/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/divbin2_unwindbound50.i -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-d966a43 [2022-01-31 13:59:36,013 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-01-31 13:59:36,017 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-01-31 13:59:36,076 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-01-31 13:59:36,077 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-01-31 13:59:36,079 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-01-31 13:59:36,081 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-01-31 13:59:36,085 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-01-31 13:59:36,086 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-01-31 13:59:36,089 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-01-31 13:59:36,090 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-01-31 13:59:36,091 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-01-31 13:59:36,091 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-01-31 13:59:36,093 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-01-31 13:59:36,094 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-01-31 13:59:36,096 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-01-31 13:59:36,096 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-01-31 13:59:36,097 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-01-31 13:59:36,098 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-01-31 13:59:36,102 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-01-31 13:59:36,103 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-01-31 13:59:36,104 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-01-31 13:59:36,105 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-01-31 13:59:36,106 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-01-31 13:59:36,110 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-01-31 13:59:36,111 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-01-31 13:59:36,111 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-01-31 13:59:36,112 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-01-31 13:59:36,112 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-01-31 13:59:36,113 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-01-31 13:59:36,113 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-01-31 13:59:36,113 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-01-31 13:59:36,115 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-01-31 13:59:36,115 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-01-31 13:59:36,116 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-01-31 13:59:36,116 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-01-31 13:59:36,117 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-01-31 13:59:36,117 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-01-31 13:59:36,117 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-01-31 13:59:36,117 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-01-31 13:59:36,118 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-01-31 13:59:36,119 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-01-31 13:59:36,129 INFO L113 SettingsManager]: Loading preferences was successful [2022-01-31 13:59:36,129 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-01-31 13:59:36,130 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-01-31 13:59:36,130 INFO L138 SettingsManager]: * sizeof long=4 [2022-01-31 13:59:36,131 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-01-31 13:59:36,131 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-01-31 13:59:36,131 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-01-31 13:59:36,131 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-01-31 13:59:36,131 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-01-31 13:59:36,131 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * sizeof long double=12 [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * Use constant arrays=true [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-01-31 13:59:36,132 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-31 13:59:36,132 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-01-31 13:59:36,132 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-01-31 13:59:36,133 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-01-31 13:59:36,133 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-01-31 13:59:36,350 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-01-31 13:59:36,384 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-01-31 13:59:36,386 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-01-31 13:59:36,387 INFO L271 PluginConnector]: Initializing CDTParser... [2022-01-31 13:59:36,387 INFO L275 PluginConnector]: CDTParser initialized [2022-01-31 13:59:36,388 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound50.i [2022-01-31 13:59:36,436 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/03d23a9b7/e356aa3685784a2191ff73a7737bf78b/FLAG50fbec0de [2022-01-31 13:59:36,775 INFO L306 CDTParser]: Found 1 translation units. [2022-01-31 13:59:36,775 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound50.i [2022-01-31 13:59:36,780 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/03d23a9b7/e356aa3685784a2191ff73a7737bf78b/FLAG50fbec0de [2022-01-31 13:59:36,794 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/03d23a9b7/e356aa3685784a2191ff73a7737bf78b [2022-01-31 13:59:36,797 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-01-31 13:59:36,798 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-01-31 13:59:36,799 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-01-31 13:59:36,799 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-01-31 13:59:36,802 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-01-31 13:59:36,803 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:36,804 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@705a6a42 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36, skipping insertion in model container [2022-01-31 13:59:36,804 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:36,810 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-01-31 13:59:36,823 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-01-31 13:59:36,961 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/divbin2_unwindbound50.i[951,964] [2022-01-31 13:59:36,970 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-31 13:59:36,977 INFO L203 MainTranslator]: Completed pre-run [2022-01-31 13:59:36,985 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/divbin2_unwindbound50.i[951,964] [2022-01-31 13:59:36,988 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-01-31 13:59:36,997 INFO L208 MainTranslator]: Completed translation [2022-01-31 13:59:36,997 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36 WrapperNode [2022-01-31 13:59:36,997 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-01-31 13:59:36,998 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-01-31 13:59:36,998 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-01-31 13:59:36,998 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-01-31 13:59:37,007 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,007 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,012 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,013 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,016 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,018 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,019 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,020 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-01-31 13:59:37,021 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-01-31 13:59:37,021 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-01-31 13:59:37,021 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-01-31 13:59:37,022 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (1/1) ... [2022-01-31 13:59:37,038 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-01-31 13:59:37,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:37,064 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-01-31 13:59:37,071 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-01-31 13:59:37,091 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-01-31 13:59:37,091 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-01-31 13:59:37,091 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-01-31 13:59:37,092 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-01-31 13:59:37,092 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-01-31 13:59:37,092 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-01-31 13:59:37,092 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-01-31 13:59:37,092 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-01-31 13:59:37,092 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_perror_fail [2022-01-31 13:59:37,092 INFO L130 BoogieDeclarations]: Found specification of procedure __assert [2022-01-31 13:59:37,092 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-01-31 13:59:37,092 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-01-31 13:59:37,093 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-01-31 13:59:37,139 INFO L234 CfgBuilder]: Building ICFG [2022-01-31 13:59:37,141 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-01-31 13:59:37,231 INFO L275 CfgBuilder]: Performing block encoding [2022-01-31 13:59:37,236 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-01-31 13:59:37,236 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-01-31 13:59:37,237 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 01:59:37 BoogieIcfgContainer [2022-01-31 13:59:37,237 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-01-31 13:59:37,238 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-01-31 13:59:37,238 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-01-31 13:59:37,239 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-01-31 13:59:37,241 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 01:59:37" (1/1) ... [2022-01-31 13:59:37,258 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 31.01 01:59:37 BasicIcfg [2022-01-31 13:59:37,259 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-01-31 13:59:37,260 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-01-31 13:59:37,260 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-01-31 13:59:37,262 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-01-31 13:59:37,262 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.01 01:59:36" (1/4) ... [2022-01-31 13:59:37,263 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38001353 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.01 01:59:37, skipping insertion in model container [2022-01-31 13:59:37,263 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 01:59:36" (2/4) ... [2022-01-31 13:59:37,263 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38001353 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.01 01:59:37, skipping insertion in model container [2022-01-31 13:59:37,263 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 01:59:37" (3/4) ... [2022-01-31 13:59:37,263 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38001353 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 31.01 01:59:37, skipping insertion in model container [2022-01-31 13:59:37,263 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 31.01 01:59:37" (4/4) ... [2022-01-31 13:59:37,264 INFO L111 eAbstractionObserver]: Analyzing ICFG divbin2_unwindbound50.iJordan [2022-01-31 13:59:37,272 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-01-31 13:59:37,272 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-01-31 13:59:37,311 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-01-31 13:59:37,315 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-01-31 13:59:37,316 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-01-31 13:59:37,325 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-01-31 13:59:37,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-01-31 13:59:37,330 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:37,330 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:37,331 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:37,334 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:37,334 INFO L85 PathProgramCache]: Analyzing trace with hash 2097950667, now seen corresponding path program 1 times [2022-01-31 13:59:37,340 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:37,340 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [19648457] [2022-01-31 13:59:37,340 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:37,341 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:37,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:37,495 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 13:59:37,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:37,503 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:37,504 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:37,504 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [19648457] [2022-01-31 13:59:37,504 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [19648457] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 13:59:37,504 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 13:59:37,505 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-01-31 13:59:37,506 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1544269652] [2022-01-31 13:59:37,506 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 13:59:37,509 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-01-31 13:59:37,509 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:37,551 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-01-31 13:59:37,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-01-31 13:59:37,553 INFO L87 Difference]: Start difference. First operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:37,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:37,627 INFO L93 Difference]: Finished difference Result 27 states and 32 transitions. [2022-01-31 13:59:37,628 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-01-31 13:59:37,629 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-01-31 13:59:37,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:37,647 INFO L225 Difference]: With dead ends: 27 [2022-01-31 13:59:37,647 INFO L226 Difference]: Without dead ends: 22 [2022-01-31 13:59:37,648 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 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-01-31 13:59:37,651 INFO L933 BasicCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:37,651 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 34 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-01-31 13:59:37,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2022-01-31 13:59:37,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2022-01-31 13:59:37,679 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-31 13:59:37,679 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 26 transitions. [2022-01-31 13:59:37,680 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 26 transitions. Word has length 12 [2022-01-31 13:59:37,680 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:37,681 INFO L470 AbstractCegarLoop]: Abstraction has 21 states and 26 transitions. [2022-01-31 13:59:37,681 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:37,681 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 26 transitions. [2022-01-31 13:59:37,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-01-31 13:59:37,681 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:37,681 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:37,682 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-01-31 13:59:37,682 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:37,682 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:37,682 INFO L85 PathProgramCache]: Analyzing trace with hash 923003056, now seen corresponding path program 1 times [2022-01-31 13:59:37,683 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:37,683 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [525648378] [2022-01-31 13:59:37,683 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:37,683 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:37,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:37,728 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-01-31 13:59:37,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:37,737 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:37,737 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:37,737 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [525648378] [2022-01-31 13:59:37,738 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [525648378] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 13:59:37,738 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 13:59:37,738 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-01-31 13:59:37,738 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1521331051] [2022-01-31 13:59:37,738 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 13:59:37,739 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-01-31 13:59:37,739 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:37,740 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-01-31 13:59:37,740 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-01-31 13:59:37,740 INFO L87 Difference]: Start difference. First operand 21 states and 26 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:37,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:37,817 INFO L93 Difference]: Finished difference Result 23 states and 28 transitions. [2022-01-31 13:59:37,818 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-01-31 13:59:37,818 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-01-31 13:59:37,818 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:37,819 INFO L225 Difference]: With dead ends: 23 [2022-01-31 13:59:37,819 INFO L226 Difference]: Without dead ends: 23 [2022-01-31 13:59:37,819 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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-01-31 13:59:37,820 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:37,821 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 53 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:37,821 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2022-01-31 13:59:37,823 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2022-01-31 13:59:37,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-31 13:59:37,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 28 transitions. [2022-01-31 13:59:37,824 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 28 transitions. Word has length 14 [2022-01-31 13:59:37,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:37,824 INFO L470 AbstractCegarLoop]: Abstraction has 23 states and 28 transitions. [2022-01-31 13:59:37,824 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:37,824 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 28 transitions. [2022-01-31 13:59:37,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-01-31 13:59:37,825 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:37,825 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:37,825 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-01-31 13:59:37,825 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:37,826 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:37,826 INFO L85 PathProgramCache]: Analyzing trace with hash 1207414063, now seen corresponding path program 1 times [2022-01-31 13:59:37,826 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:37,826 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1932702057] [2022-01-31 13:59:37,826 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:37,826 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:37,837 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:37,837 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1887717050] [2022-01-31 13:59:37,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:37,838 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:37,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:37,839 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-01-31 13:59:37,841 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-01-31 13:59:37,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:37,888 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 7 conjunts are in the unsatisfiable core [2022-01-31 13:59:37,892 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:37,952 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:37,952 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-31 13:59:37,952 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:37,952 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1932702057] [2022-01-31 13:59:37,952 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:37,953 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1887717050] [2022-01-31 13:59:37,953 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1887717050] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 13:59:37,953 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 13:59:37,953 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-01-31 13:59:37,953 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [615717762] [2022-01-31 13:59:37,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 13:59:37,954 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-01-31 13:59:37,954 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:37,954 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-01-31 13:59:37,954 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-01-31 13:59:37,954 INFO L87 Difference]: Start difference. First operand 23 states and 28 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:37,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:37,967 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2022-01-31 13:59:37,968 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-01-31 13:59:37,968 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-01-31 13:59:37,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:37,968 INFO L225 Difference]: With dead ends: 27 [2022-01-31 13:59:37,969 INFO L226 Difference]: Without dead ends: 27 [2022-01-31 13:59:37,969 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-01-31 13:59:37,970 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 3 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:37,970 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 81 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:37,970 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-01-31 13:59:37,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-01-31 13:59:37,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-31 13:59:37,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2022-01-31 13:59:37,973 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 15 [2022-01-31 13:59:37,973 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:37,973 INFO L470 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2022-01-31 13:59:37,973 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:37,974 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2022-01-31 13:59:37,974 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-01-31 13:59:37,974 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:37,974 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:37,994 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-01-31 13:59:38,193 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:38,194 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:38,194 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:38,194 INFO L85 PathProgramCache]: Analyzing trace with hash 1208546121, now seen corresponding path program 1 times [2022-01-31 13:59:38,194 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:38,194 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [228074731] [2022-01-31 13:59:38,195 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:38,195 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:38,204 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:38,204 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [35598188] [2022-01-31 13:59:38,205 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:38,205 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:38,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:38,214 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-01-31 13:59:38,214 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-01-31 13:59:38,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:38,263 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 14 conjunts are in the unsatisfiable core [2022-01-31 13:59:38,265 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:38,366 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:38,366 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-31 13:59:38,366 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:38,366 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [228074731] [2022-01-31 13:59:38,366 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:38,366 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [35598188] [2022-01-31 13:59:38,367 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [35598188] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 13:59:38,367 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 13:59:38,367 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-01-31 13:59:38,367 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [98023994] [2022-01-31 13:59:38,367 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 13:59:38,367 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-31 13:59:38,367 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:38,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-31 13:59:38,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-01-31 13:59:38,368 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:38,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:38,403 INFO L93 Difference]: Finished difference Result 33 states and 40 transitions. [2022-01-31 13:59:38,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-01-31 13:59:38,403 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-01-31 13:59:38,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:38,404 INFO L225 Difference]: With dead ends: 33 [2022-01-31 13:59:38,404 INFO L226 Difference]: Without dead ends: 32 [2022-01-31 13:59:38,405 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2022-01-31 13:59:38,405 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 9 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:38,406 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 96 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:38,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-01-31 13:59:38,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-01-31 13:59:38,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-31 13:59:38,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2022-01-31 13:59:38,409 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 15 [2022-01-31 13:59:38,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:38,410 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2022-01-31 13:59:38,410 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:38,410 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2022-01-31 13:59:38,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-01-31 13:59:38,410 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:38,411 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:38,439 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-01-31 13:59:38,642 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,SelfDestructingSolverStorable3 [2022-01-31 13:59:38,643 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:38,643 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:38,643 INFO L85 PathProgramCache]: Analyzing trace with hash 1227316531, now seen corresponding path program 1 times [2022-01-31 13:59:38,643 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:38,644 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1404360236] [2022-01-31 13:59:38,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:38,644 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:38,652 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:38,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [828843061] [2022-01-31 13:59:38,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:38,652 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:38,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:38,653 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-01-31 13:59:38,655 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-01-31 13:59:38,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:38,689 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-01-31 13:59:38,690 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:38,738 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:38,739 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-31 13:59:38,805 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:38,805 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:38,805 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1404360236] [2022-01-31 13:59:38,805 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:38,805 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [828843061] [2022-01-31 13:59:38,806 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [828843061] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-31 13:59:38,806 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-31 13:59:38,806 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-01-31 13:59:38,806 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1344471998] [2022-01-31 13:59:38,806 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-31 13:59:38,807 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-01-31 13:59:38,808 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:38,829 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-01-31 13:59:38,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-01-31 13:59:38,829 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-31 13:59:38,868 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:38,868 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2022-01-31 13:59:38,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-01-31 13:59:38,869 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-01-31 13:59:38,869 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:38,869 INFO L225 Difference]: With dead ends: 54 [2022-01-31 13:59:38,869 INFO L226 Difference]: Without dead ends: 54 [2022-01-31 13:59:38,870 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-01-31 13:59:38,870 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 31 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:38,870 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 94 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:38,871 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-01-31 13:59:38,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 40. [2022-01-31 13:59:38,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 32 states have internal predecessors, (40), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-31 13:59:38,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 48 transitions. [2022-01-31 13:59:38,874 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 48 transitions. Word has length 17 [2022-01-31 13:59:38,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:38,874 INFO L470 AbstractCegarLoop]: Abstraction has 40 states and 48 transitions. [2022-01-31 13:59:38,874 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-31 13:59:38,875 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 48 transitions. [2022-01-31 13:59:38,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-01-31 13:59:38,875 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:38,875 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:38,892 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-01-31 13:59:39,091 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:39,092 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:39,093 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:39,093 INFO L85 PathProgramCache]: Analyzing trace with hash 2051197196, now seen corresponding path program 1 times [2022-01-31 13:59:39,093 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:39,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [938774416] [2022-01-31 13:59:39,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:39,093 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:39,101 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:39,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2103954073] [2022-01-31 13:59:39,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:39,102 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:39,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:39,116 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-01-31 13:59:39,124 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-01-31 13:59:39,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:39,164 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 9 conjunts are in the unsatisfiable core [2022-01-31 13:59:39,166 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:39,227 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:39,228 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-31 13:59:39,282 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:39,283 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:39,283 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [938774416] [2022-01-31 13:59:39,283 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:39,283 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103954073] [2022-01-31 13:59:39,283 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2103954073] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-31 13:59:39,283 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-31 13:59:39,283 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-01-31 13:59:39,283 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [732797196] [2022-01-31 13:59:39,283 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-31 13:59:39,284 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-01-31 13:59:39,284 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:39,284 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-01-31 13:59:39,284 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-01-31 13:59:39,285 INFO L87 Difference]: Start difference. First operand 40 states and 48 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-31 13:59:39,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:39,348 INFO L93 Difference]: Finished difference Result 84 states and 102 transitions. [2022-01-31 13:59:39,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-01-31 13:59:39,349 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-01-31 13:59:39,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:39,350 INFO L225 Difference]: With dead ends: 84 [2022-01-31 13:59:39,350 INFO L226 Difference]: Without dead ends: 84 [2022-01-31 13:59:39,350 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2022-01-31 13:59:39,351 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 79 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:39,351 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [79 Valid, 136 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:39,352 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-01-31 13:59:39,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 77. [2022-01-31 13:59:39,355 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 59 states have (on average 1.3728813559322033) internal successors, (81), 63 states have internal predecessors, (81), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-01-31 13:59:39,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 98 transitions. [2022-01-31 13:59:39,356 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 98 transitions. Word has length 18 [2022-01-31 13:59:39,356 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:39,357 INFO L470 AbstractCegarLoop]: Abstraction has 77 states and 98 transitions. [2022-01-31 13:59:39,357 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-31 13:59:39,357 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 98 transitions. [2022-01-31 13:59:39,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-01-31 13:59:39,357 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:39,357 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:39,374 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-01-31 13:59:39,574 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:39,574 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:39,575 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:39,575 INFO L85 PathProgramCache]: Analyzing trace with hash 2052329254, now seen corresponding path program 1 times [2022-01-31 13:59:39,575 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:39,575 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [707098469] [2022-01-31 13:59:39,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:39,575 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:39,583 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:39,583 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1257647362] [2022-01-31 13:59:39,584 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:39,584 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:39,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:39,594 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-01-31 13:59:39,595 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-01-31 13:59:39,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:39,649 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 14 conjunts are in the unsatisfiable core [2022-01-31 13:59:39,650 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:39,737 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:39,738 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-31 13:59:39,858 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:39,859 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:39,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [707098469] [2022-01-31 13:59:39,859 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:39,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1257647362] [2022-01-31 13:59:39,859 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1257647362] provided 1 perfect and 1 imperfect interpolant sequences [2022-01-31 13:59:39,859 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-01-31 13:59:39,859 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2022-01-31 13:59:39,860 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1555779950] [2022-01-31 13:59:39,860 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 13:59:39,860 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-01-31 13:59:39,860 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:39,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-01-31 13:59:39,860 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2022-01-31 13:59:39,860 INFO L87 Difference]: Start difference. First operand 77 states and 98 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:39,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:39,873 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2022-01-31 13:59:39,873 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-01-31 13:59:39,873 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2022-01-31 13:59:39,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:39,875 INFO L225 Difference]: With dead ends: 108 [2022-01-31 13:59:39,875 INFO L226 Difference]: Without dead ends: 108 [2022-01-31 13:59:39,875 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-01-31 13:59:39,876 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 11 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 11 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:39,876 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 104 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 11 Unchecked, 0.0s Time] [2022-01-31 13:59:39,878 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-01-31 13:59:39,890 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 107. [2022-01-31 13:59:39,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 81 states have (on average 1.2839506172839505) internal successors, (104), 89 states have internal predecessors, (104), 15 states have call successors, (15), 11 states have call predecessors, (15), 10 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) [2022-01-31 13:59:39,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 129 transitions. [2022-01-31 13:59:39,891 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 129 transitions. Word has length 18 [2022-01-31 13:59:39,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:39,891 INFO L470 AbstractCegarLoop]: Abstraction has 107 states and 129 transitions. [2022-01-31 13:59:39,892 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-01-31 13:59:39,892 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 129 transitions. [2022-01-31 13:59:39,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-01-31 13:59:39,892 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:39,892 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:39,910 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-01-31 13:59:40,109 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:40,110 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:40,110 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:40,110 INFO L85 PathProgramCache]: Analyzing trace with hash 462666167, now seen corresponding path program 1 times [2022-01-31 13:59:40,110 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:40,110 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1770578783] [2022-01-31 13:59:40,110 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:40,110 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:40,117 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:40,117 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1149520710] [2022-01-31 13:59:40,117 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:40,117 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:40,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:40,118 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-01-31 13:59:40,119 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-01-31 13:59:40,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:40,158 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 5 conjunts are in the unsatisfiable core [2022-01-31 13:59:40,159 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:40,204 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:40,204 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-01-31 13:59:40,205 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:40,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1770578783] [2022-01-31 13:59:40,205 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:40,205 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1149520710] [2022-01-31 13:59:40,205 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1149520710] provided 1 perfect and 0 imperfect interpolant sequences [2022-01-31 13:59:40,205 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-01-31 13:59:40,205 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-01-31 13:59:40,205 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [656867946] [2022-01-31 13:59:40,205 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-01-31 13:59:40,206 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-01-31 13:59:40,206 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:40,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-01-31 13:59:40,206 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-01-31 13:59:40,206 INFO L87 Difference]: Start difference. First operand 107 states and 129 transitions. Second operand has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-31 13:59:40,218 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:40,218 INFO L93 Difference]: Finished difference Result 103 states and 122 transitions. [2022-01-31 13:59:40,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-01-31 13:59:40,219 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2022-01-31 13:59:40,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:40,220 INFO L225 Difference]: With dead ends: 103 [2022-01-31 13:59:40,220 INFO L226 Difference]: Without dead ends: 93 [2022-01-31 13:59:40,220 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 22 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-01-31 13:59:40,221 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:40,221 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:40,221 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-01-31 13:59:40,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-01-31 13:59:40,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 71 states have (on average 1.2816901408450705) internal successors, (91), 77 states have internal predecessors, (91), 13 states have call successors, (13), 10 states have call predecessors, (13), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-31 13:59:40,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 112 transitions. [2022-01-31 13:59:40,226 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 112 transitions. Word has length 24 [2022-01-31 13:59:40,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:40,227 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 112 transitions. [2022-01-31 13:59:40,227 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-01-31 13:59:40,227 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 112 transitions. [2022-01-31 13:59:40,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-01-31 13:59:40,227 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:40,227 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:40,269 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-01-31 13:59:40,472 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:40,472 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:40,472 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:40,473 INFO L85 PathProgramCache]: Analyzing trace with hash 1651364104, now seen corresponding path program 1 times [2022-01-31 13:59:40,473 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:40,473 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [102082281] [2022-01-31 13:59:40,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:40,473 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:40,482 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:40,483 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [876415681] [2022-01-31 13:59:40,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:40,483 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:40,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:40,484 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-01-31 13:59:40,485 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-01-31 13:59:40,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:40,513 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-01-31 13:59:40,514 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:40,568 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-31 13:59:40,569 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-31 13:59:40,647 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-01-31 13:59:40,647 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 13:59:40,648 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [102082281] [2022-01-31 13:59:40,648 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 13:59:40,648 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [876415681] [2022-01-31 13:59:40,648 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [876415681] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-31 13:59:40,648 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-31 13:59:40,648 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2022-01-31 13:59:40,648 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1082644265] [2022-01-31 13:59:40,648 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-31 13:59:40,648 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-01-31 13:59:40,648 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 13:59:40,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-01-31 13:59:40,649 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-01-31 13:59:40,649 INFO L87 Difference]: Start difference. First operand 93 states and 112 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-31 13:59:40,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 13:59:40,711 INFO L93 Difference]: Finished difference Result 106 states and 121 transitions. [2022-01-31 13:59:40,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-01-31 13:59:40,714 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-01-31 13:59:40,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 13:59:40,714 INFO L225 Difference]: With dead ends: 106 [2022-01-31 13:59:40,715 INFO L226 Difference]: Without dead ends: 88 [2022-01-31 13:59:40,715 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2022-01-31 13:59:40,715 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 17 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-01-31 13:59:40,715 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 92 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-01-31 13:59:40,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-01-31 13:59:40,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-01-31 13:59:40,719 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 69 states have (on average 1.2318840579710144) internal successors, (85), 73 states have internal predecessors, (85), 10 states have call successors, (10), 9 states have call predecessors, (10), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-31 13:59:40,720 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 103 transitions. [2022-01-31 13:59:40,720 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 103 transitions. Word has length 24 [2022-01-31 13:59:40,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 13:59:40,720 INFO L470 AbstractCegarLoop]: Abstraction has 88 states and 103 transitions. [2022-01-31 13:59:40,720 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-01-31 13:59:40,720 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 103 transitions. [2022-01-31 13:59:40,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-01-31 13:59:40,721 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 13:59:40,721 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 13:59:40,753 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-01-31 13:59:40,937 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:40,937 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 13:59:40,938 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 13:59:40,938 INFO L85 PathProgramCache]: Analyzing trace with hash -268589446, now seen corresponding path program 1 times [2022-01-31 13:59:40,938 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 13:59:40,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [439991035] [2022-01-31 13:59:40,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:40,938 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 13:59:40,948 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 13:59:40,949 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [953506739] [2022-01-31 13:59:40,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 13:59:40,949 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 13:59:40,949 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 13:59:40,963 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-01-31 13:59:41,004 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-01-31 13:59:41,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-01-31 13:59:41,062 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 25 conjunts are in the unsatisfiable core [2022-01-31 13:59:41,063 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-01-31 13:59:41,282 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-01-31 13:59:41,282 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-01-31 13:59:51,913 WARN L860 $PredicateComparison]: unable to prove that (let ((.cse0 (mod c_main_~b~0 4294967296))) (or (= (mod c_main_~A~0 4294967296) (mod (+ (* (div .cse0 2) (* c_main_~q~0 2)) c_main_~r~0) 4294967296)) (<= .cse0 (mod c_main_~r~0 4294967296)))) is different from true [2022-01-31 14:00:04,699 WARN L860 $PredicateComparison]: unable to prove that (let ((.cse1 (mod (* c_main_~b~0 2) 4294967296)) (.cse0 (mod c_main_~r~0 4294967296))) (or (not (<= (mod c_main_~b~0 4294967296) .cse0)) (= (mod c_main_~A~0 4294967296) (mod (+ (* (div .cse1 2) (* c_main_~q~0 2)) c_main_~r~0) 4294967296)) (<= .cse1 .cse0))) is different from true [2022-01-31 14:00:19,563 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2022-01-31 14:00:19,563 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-01-31 14:00:19,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [439991035] [2022-01-31 14:00:19,564 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-01-31 14:00:19,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [953506739] [2022-01-31 14:00:19,564 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [953506739] provided 0 perfect and 2 imperfect interpolant sequences [2022-01-31 14:00:19,564 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-01-31 14:00:19,564 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 13 [2022-01-31 14:00:19,564 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [211031781] [2022-01-31 14:00:19,564 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-01-31 14:00:19,564 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-01-31 14:00:19,564 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-01-31 14:00:19,565 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-01-31 14:00:19,565 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=81, Unknown=3, NotChecked=38, Total=156 [2022-01-31 14:00:19,565 INFO L87 Difference]: Start difference. First operand 88 states and 103 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-31 14:00:30,098 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-01-31 14:00:32,200 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.10s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-01-31 14:00:34,368 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-01-31 14:00:36,512 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-01-31 14:00:38,544 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-01-31 14:00:38,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-01-31 14:00:38,713 INFO L93 Difference]: Finished difference Result 98 states and 112 transitions. [2022-01-31 14:00:38,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-01-31 14:00:38,713 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 27 [2022-01-31 14:00:38,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-01-31 14:00:38,714 INFO L225 Difference]: With dead ends: 98 [2022-01-31 14:00:38,714 INFO L226 Difference]: Without dead ends: 98 [2022-01-31 14:00:38,714 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 40 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 15.0s TimeCoverageRelationStatistics Valid=46, Invalid=113, Unknown=5, NotChecked=46, Total=210 [2022-01-31 14:00:38,715 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 22 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 9 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 89 IncrementalHoareTripleChecker+Unchecked, 10.6s IncrementalHoareTripleChecker+Time [2022-01-31 14:00:38,715 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 140 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 84 Invalid, 5 Unknown, 89 Unchecked, 10.6s Time] [2022-01-31 14:00:38,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-01-31 14:00:38,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 90. [2022-01-31 14:00:38,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 10 states have call successors, (10), 9 states have call predecessors, (10), 8 states have return successors, (8), 6 states have call predecessors, (8), 8 states have call successors, (8) [2022-01-31 14:00:38,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 104 transitions. [2022-01-31 14:00:38,719 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 104 transitions. Word has length 27 [2022-01-31 14:00:38,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-01-31 14:00:38,719 INFO L470 AbstractCegarLoop]: Abstraction has 90 states and 104 transitions. [2022-01-31 14:00:38,719 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-01-31 14:00:38,719 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 104 transitions. [2022-01-31 14:00:38,720 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-01-31 14:00:38,720 INFO L506 BasicCegarLoop]: Found error trace [2022-01-31 14:00:38,720 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-01-31 14:00:38,744 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-01-31 14:00:38,935 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,SelfDestructingSolverStorable9 [2022-01-31 14:00:38,936 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-01-31 14:00:38,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-01-31 14:00:38,936 INFO L85 PathProgramCache]: Analyzing trace with hash -142927336, now seen corresponding path program 1 times [2022-01-31 14:00:38,936 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-01-31 14:00:38,936 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1843130996] [2022-01-31 14:00:38,936 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 14:00:38,936 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-01-31 14:00:38,948 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-01-31 14:00:38,948 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [934794163] [2022-01-31 14:00:38,948 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-01-31 14:00:38,948 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-01-31 14:00:38,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-01-31 14:00:38,949 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-01-31 14:00:38,950 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process