./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 839c364b Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/config/TaipanReach.xml -i ../../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7 --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 10aecdd717bb6691571ad1da0b912f030832fb85361f767ea82293acfe046216 --- Real Ultimate output --- This is Ultimate 0.2.2-hotfix-svcomp22-839c364 [2021-11-25 19:08:43,970 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-25 19:08:43,973 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-25 19:08:44,038 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-25 19:08:44,039 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-25 19:08:44,040 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-25 19:08:44,042 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-25 19:08:44,045 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-25 19:08:44,047 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-25 19:08:44,049 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-25 19:08:44,050 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-25 19:08:44,051 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-25 19:08:44,052 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-25 19:08:44,053 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-25 19:08:44,055 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-25 19:08:44,057 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-25 19:08:44,058 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-25 19:08:44,059 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-25 19:08:44,062 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-25 19:08:44,064 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-25 19:08:44,067 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-25 19:08:44,069 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-25 19:08:44,070 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-25 19:08:44,071 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-25 19:08:44,076 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-25 19:08:44,076 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-25 19:08:44,077 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-25 19:08:44,078 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-25 19:08:44,079 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-25 19:08:44,080 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-25 19:08:44,081 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-25 19:08:44,082 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-25 19:08:44,083 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-25 19:08:44,084 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-25 19:08:44,085 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-25 19:08:44,086 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-25 19:08:44,087 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-25 19:08:44,087 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-25 19:08:44,088 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-25 19:08:44,089 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-25 19:08:44,090 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-25 19:08:44,091 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-25 19:08:44,123 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-25 19:08:44,123 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-25 19:08:44,124 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-25 19:08:44,124 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-25 19:08:44,125 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-25 19:08:44,125 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-25 19:08:44,125 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-25 19:08:44,125 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-25 19:08:44,126 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-25 19:08:44,126 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-25 19:08:44,126 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-25 19:08:44,126 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-25 19:08:44,127 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-25 19:08:44,127 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-25 19:08:44,127 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-25 19:08:44,127 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-25 19:08:44,127 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-25 19:08:44,128 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2021-11-25 19:08:44,129 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-25 19:08:44,129 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-25 19:08:44,129 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-25 19:08:44,129 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-25 19:08:44,130 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-25 19:08:44,130 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-25 19:08:44,130 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-25 19:08:44,130 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-25 19:08:44,130 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-25 19:08:44,131 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-25 19:08:44,131 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-25 19:08:44,131 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-25 19:08:44,131 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-25 19:08:44,132 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-25 19:08:44,132 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 19:08:44,132 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-25 19:08:44,132 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-25 19:08:44,133 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-25 19:08:44,133 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-25 19:08:44,133 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-25 19:08:44,133 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-25 19:08:44,134 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-25 19:08:44,134 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-25 19:08:44,134 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/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.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7 Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 10aecdd717bb6691571ad1da0b912f030832fb85361f767ea82293acfe046216 [2021-11-25 19:08:44,439 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-25 19:08:44,473 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-25 19:08:44,476 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-25 19:08:44,478 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-25 19:08:44,479 INFO L275 PluginConnector]: CDTParser initialized [2021-11-25 19:08:44,480 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/../../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i [2021-11-25 19:08:44,574 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/data/683c06810/6979decdfdee414d92200ae661888b78/FLAG210a813e6 [2021-11-25 19:08:45,186 INFO L306 CDTParser]: Found 1 translation units. [2021-11-25 19:08:45,186 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i [2021-11-25 19:08:45,214 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/data/683c06810/6979decdfdee414d92200ae661888b78/FLAG210a813e6 [2021-11-25 19:08:45,450 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/data/683c06810/6979decdfdee414d92200ae661888b78 [2021-11-25 19:08:45,453 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-25 19:08:45,455 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-25 19:08:45,459 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-25 19:08:45,462 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-25 19:08:45,466 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-25 19:08:45,467 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 07:08:45" (1/1) ... [2021-11-25 19:08:45,469 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3596597e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:45, skipping insertion in model container [2021-11-25 19:08:45,472 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.11 07:08:45" (1/1) ... [2021-11-25 19:08:45,480 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-25 19:08:45,546 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-25 19:08:45,961 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2021-11-25 19:08:45,972 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2021-11-25 19:08:45,976 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2021-11-25 19:08:45,994 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 19:08:46,010 INFO L203 MainTranslator]: Completed pre-run [2021-11-25 19:08:46,101 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2021-11-25 19:08:46,102 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2021-11-25 19:08:46,103 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2021-11-25 19:08:46,112 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-25 19:08:46,176 INFO L208 MainTranslator]: Completed translation [2021-11-25 19:08:46,176 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46 WrapperNode [2021-11-25 19:08:46,177 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-25 19:08:46,179 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-25 19:08:46,179 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-25 19:08:46,180 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-25 19:08:46,187 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,206 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,241 INFO L137 Inliner]: procedures = 142, calls = 62, calls flagged for inlining = 15, calls inlined = 14, statements flattened = 161 [2021-11-25 19:08:46,242 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-25 19:08:46,243 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-25 19:08:46,243 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-25 19:08:46,243 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-25 19:08:46,252 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,253 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,260 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,260 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,275 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,281 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,284 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,290 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-25 19:08:46,291 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-25 19:08:46,291 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-25 19:08:46,291 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-25 19:08:46,292 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (1/1) ... [2021-11-25 19:08:46,305 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-25 19:08:46,326 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:08:46,343 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-25 19:08:46,348 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-25 19:08:46,384 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2021-11-25 19:08:46,384 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2021-11-25 19:08:46,384 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_list_add [2021-11-25 19:08:46,385 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_list_add [2021-11-25 19:08:46,385 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-11-25 19:08:46,385 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-25 19:08:46,385 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-11-25 19:08:46,385 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2021-11-25 19:08:46,385 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2021-11-25 19:08:46,386 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-11-25 19:08:46,386 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-11-25 19:08:46,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-11-25 19:08:46,386 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-25 19:08:46,386 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2021-11-25 19:08:46,387 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2021-11-25 19:08:46,387 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-25 19:08:46,387 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-25 19:08:46,520 INFO L236 CfgBuilder]: Building ICFG [2021-11-25 19:08:46,521 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-25 19:08:46,957 INFO L277 CfgBuilder]: Performing block encoding [2021-11-25 19:08:47,086 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-25 19:08:47,087 INFO L301 CfgBuilder]: Removed 5 assume(true) statements. [2021-11-25 19:08:47,089 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 07:08:47 BoogieIcfgContainer [2021-11-25 19:08:47,090 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-25 19:08:47,093 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-25 19:08:47,095 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-25 19:08:47,099 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-25 19:08:47,100 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.11 07:08:45" (1/3) ... [2021-11-25 19:08:47,101 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58b3e90f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 07:08:47, skipping insertion in model container [2021-11-25 19:08:47,101 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.11 07:08:46" (2/3) ... [2021-11-25 19:08:47,102 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58b3e90f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.11 07:08:47, skipping insertion in model container [2021-11-25 19:08:47,103 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.11 07:08:47" (3/3) ... [2021-11-25 19:08:47,104 INFO L111 eAbstractionObserver]: Analyzing ICFG test_mutex_unbounded-1.i [2021-11-25 19:08:47,110 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-25 19:08:47,111 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 3 error locations. [2021-11-25 19:08:47,164 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-25 19:08:47,172 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR [2021-11-25 19:08:47,172 INFO L340 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2021-11-25 19:08:47,196 INFO L276 IsEmpty]: Start isEmpty. Operand has 46 states, 30 states have (on average 1.4333333333333333) internal successors, (43), 34 states have internal predecessors, (43), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2021-11-25 19:08:47,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2021-11-25 19:08:47,206 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:08:47,206 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2021-11-25 19:08:47,207 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:08:47,212 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:08:47,213 INFO L85 PathProgramCache]: Analyzing trace with hash -1976968745, now seen corresponding path program 1 times [2021-11-25 19:08:47,231 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:08:47,233 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [739923541] [2021-11-25 19:08:47,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:08:47,235 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:08:47,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:08:47,542 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:08:47,542 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:08:47,543 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [739923541] [2021-11-25 19:08:47,544 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [739923541] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:08:47,544 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:08:47,544 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-11-25 19:08:47,547 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [665710271] [2021-11-25 19:08:47,547 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:08:47,553 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-25 19:08:47,553 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:08:47,591 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-25 19:08:47,592 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-25 19:08:47,594 INFO L87 Difference]: Start difference. First operand has 46 states, 30 states have (on average 1.4333333333333333) internal successors, (43), 34 states have internal predecessors, (43), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-25 19:08:47,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:08:47,858 INFO L93 Difference]: Finished difference Result 124 states and 161 transitions. [2021-11-25 19:08:47,860 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-11-25 19:08:47,862 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2021-11-25 19:08:47,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:08:47,875 INFO L225 Difference]: With dead ends: 124 [2021-11-25 19:08:47,876 INFO L226 Difference]: Without dead ends: 79 [2021-11-25 19:08:47,881 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-11-25 19:08:47,888 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 41 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-11-25 19:08:47,890 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 122 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-11-25 19:08:47,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2021-11-25 19:08:47,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 65. [2021-11-25 19:08:47,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 46 states have (on average 1.3695652173913044) internal successors, (63), 49 states have internal predecessors, (63), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2021-11-25 19:08:47,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 85 transitions. [2021-11-25 19:08:47,941 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 85 transitions. Word has length 6 [2021-11-25 19:08:47,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:08:47,942 INFO L470 AbstractCegarLoop]: Abstraction has 65 states and 85 transitions. [2021-11-25 19:08:47,942 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-25 19:08:47,942 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 85 transitions. [2021-11-25 19:08:47,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-11-25 19:08:47,944 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:08:47,945 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:08:47,945 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-25 19:08:47,945 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:08:47,946 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:08:47,946 INFO L85 PathProgramCache]: Analyzing trace with hash -1295928281, now seen corresponding path program 1 times [2021-11-25 19:08:47,947 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:08:47,947 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [340126502] [2021-11-25 19:08:47,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:08:47,947 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:08:47,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:08:48,023 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:08:48,023 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:08:48,024 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [340126502] [2021-11-25 19:08:48,024 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [340126502] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:08:48,025 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:08:48,026 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-11-25 19:08:48,026 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [777847007] [2021-11-25 19:08:48,026 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:08:48,028 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-25 19:08:48,029 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:08:48,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-25 19:08:48,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-25 19:08:48,040 INFO L87 Difference]: Start difference. First operand 65 states and 85 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-25 19:08:48,163 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:08:48,164 INFO L93 Difference]: Finished difference Result 75 states and 100 transitions. [2021-11-25 19:08:48,165 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-11-25 19:08:48,166 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-11-25 19:08:48,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:08:48,168 INFO L225 Difference]: With dead ends: 75 [2021-11-25 19:08:48,168 INFO L226 Difference]: Without dead ends: 73 [2021-11-25 19:08:48,169 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-25 19:08:48,170 INFO L933 BasicCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 19:08:48,171 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 117 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 19:08:48,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2021-11-25 19:08:48,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 73. [2021-11-25 19:08:48,201 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 52 states have (on average 1.3269230769230769) internal successors, (69), 55 states have internal predecessors, (69), 11 states have call successors, (11), 5 states have call predecessors, (11), 7 states have return successors, (17), 13 states have call predecessors, (17), 11 states have call successors, (17) [2021-11-25 19:08:48,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 97 transitions. [2021-11-25 19:08:48,203 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 97 transitions. Word has length 11 [2021-11-25 19:08:48,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:08:48,204 INFO L470 AbstractCegarLoop]: Abstraction has 73 states and 97 transitions. [2021-11-25 19:08:48,204 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-25 19:08:48,204 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 97 transitions. [2021-11-25 19:08:48,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2021-11-25 19:08:48,205 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:08:48,205 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:08:48,206 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-11-25 19:08:48,206 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:08:48,207 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:08:48,207 INFO L85 PathProgramCache]: Analyzing trace with hash -349854364, now seen corresponding path program 1 times [2021-11-25 19:08:48,207 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:08:48,207 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1937954571] [2021-11-25 19:08:48,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:08:48,208 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:08:48,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:08:48,364 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:08:48,365 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:08:48,366 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1937954571] [2021-11-25 19:08:48,366 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1937954571] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:08:48,366 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-25 19:08:48,366 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-11-25 19:08:48,366 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1381459445] [2021-11-25 19:08:48,367 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:08:48,367 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-25 19:08:48,367 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:08:48,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-25 19:08:48,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-25 19:08:48,369 INFO L87 Difference]: Start difference. First operand 73 states and 97 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-25 19:08:48,552 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:08:48,552 INFO L93 Difference]: Finished difference Result 125 states and 161 transitions. [2021-11-25 19:08:48,553 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-11-25 19:08:48,553 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2021-11-25 19:08:48,554 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:08:48,555 INFO L225 Difference]: With dead ends: 125 [2021-11-25 19:08:48,555 INFO L226 Difference]: Without dead ends: 57 [2021-11-25 19:08:48,556 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-11-25 19:08:48,558 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 11 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-25 19:08:48,558 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 113 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-25 19:08:48,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2021-11-25 19:08:48,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 52. [2021-11-25 19:08:48,579 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 34 states have (on average 1.2647058823529411) internal successors, (43), 38 states have internal predecessors, (43), 9 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) [2021-11-25 19:08:48,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 64 transitions. [2021-11-25 19:08:48,582 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 64 transitions. Word has length 12 [2021-11-25 19:08:48,583 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:08:48,583 INFO L470 AbstractCegarLoop]: Abstraction has 52 states and 64 transitions. [2021-11-25 19:08:48,583 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-11-25 19:08:48,583 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 64 transitions. [2021-11-25 19:08:48,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2021-11-25 19:08:48,585 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:08:48,585 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:08:48,586 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2021-11-25 19:08:48,587 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:08:48,589 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:08:48,589 INFO L85 PathProgramCache]: Analyzing trace with hash -462529757, now seen corresponding path program 1 times [2021-11-25 19:08:48,589 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:08:48,591 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680039606] [2021-11-25 19:08:48,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:08:48,592 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:08:48,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:08:48,945 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:08:48,946 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:08:48,946 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680039606] [2021-11-25 19:08:48,946 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [680039606] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:08:48,946 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [91985448] [2021-11-25 19:08:48,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:08:48,947 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:08:48,947 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:08:48,952 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:08:48,980 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-25 19:08:49,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:08:49,132 INFO L263 TraceCheckSpWp]: Trace formula consists of 278 conjuncts, 50 conjunts are in the unsatisfiable core [2021-11-25 19:08:49,148 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:08:49,429 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-11-25 19:08:49,430 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-11-25 19:08:49,811 INFO L354 Elim1Store]: treesize reduction 117, result has 35.4 percent of original size [2021-11-25 19:08:49,812 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 194 treesize of output 182 [2021-11-25 19:08:49,829 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:08:49,847 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:08:49,900 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:08:50,641 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:08:50,642 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 34 treesize of output 36 [2021-11-25 19:08:50,772 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2021-11-25 19:08:50,779 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:50,919 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:08:50,970 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:08:50,997 INFO L354 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2021-11-25 19:08:50,997 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 26 [2021-11-25 19:08:51,005 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:08:51,036 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2021-11-25 19:08:51,040 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:51,199 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2021-11-25 19:08:51,229 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:08:51,230 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:08:51,575 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:08:51,576 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 1502 treesize of output 1471 [2021-11-25 19:08:51,620 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1814 treesize of output 1750 [2021-11-25 19:08:51,655 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1926 treesize of output 1894 [2021-11-25 19:08:51,691 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1894 treesize of output 1886 [2021-11-25 19:08:51,726 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1886 treesize of output 1870 [2021-11-25 19:08:52,100 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:08:52,101 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,103 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 28 [2021-11-25 19:08:52,108 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,115 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,260 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:08:52,261 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [91985448] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:08:52,261 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [710323991] [2021-11-25 19:08:52,283 INFO L159 IcfgInterpreter]: Started Sifa with 19 locations of interest [2021-11-25 19:08:52,284 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:08:52,289 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:08:52,296 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:08:52,296 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:08:52,386 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:08:52,392 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:08:52,571 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,669 INFO L354 Elim1Store]: treesize reduction 140, result has 30.3 percent of original size [2021-11-25 19:08:52,670 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2021-11-25 19:08:52,734 INFO L354 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2021-11-25 19:08:52,735 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 19 [2021-11-25 19:08:52,771 INFO L354 Elim1Store]: treesize reduction 33, result has 34.0 percent of original size [2021-11-25 19:08:52,772 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 39 treesize of output 31 [2021-11-25 19:08:52,806 INFO L354 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2021-11-25 19:08:52,806 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 31 [2021-11-25 19:08:52,830 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,902 INFO L354 Elim1Store]: treesize reduction 159, result has 20.9 percent of original size [2021-11-25 19:08:52,902 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2021-11-25 19:08:52,931 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:08:52,935 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:08:52,950 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:08:52,954 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:08:52,980 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,981 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,982 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:52,993 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,994 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:52,995 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,035 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,036 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,037 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,047 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,048 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,049 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,116 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,126 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,170 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,179 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,426 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,427 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,428 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,437 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,438 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,440 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,639 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,640 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,641 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,651 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,653 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:08:53,654 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:08:53,949 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,963 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,975 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:53,984 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:54,174 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:54,183 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:54,197 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:54,209 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:08:55,189 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 27 for LOIs [2021-11-25 19:08:55,196 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 34 for LOIs [2021-11-25 19:08:55,280 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2021-11-25 19:08:55,332 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:09:01,870 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '915#(and (<= |~#mutexes~0.offset| 0) (<= |~#drvlist~0.offset| 0) (<= 0 |~#drvlist~0.offset|) (<= 0 |ULTIMATE.start_foo_~me~0#1.offset|) (<= 0 |#NULL.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |~#mutexes~0.offset|) (= |ULTIMATE.start_foo_~__mptr~5#1.base| (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_ldv_list_empty_#res#1| |ULTIMATE.start_ldv_set_empty_#res#1|) (<= |ULTIMATE.start_foo_~N~0#1| |ULTIMATE.start_foo_~i~0#1|) (= (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|) |ULTIMATE.start_foo_~__mptr~7#1.base|) (<= 0 |~#mutexes~0.offset|) (= (ite (and (= (select (select |#memory_$Pointer$.offset| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| (select (select |#memory_$Pointer$.base| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|))) 1 0) |ULTIMATE.start_ldv_list_empty_#res#1|) (<= |#NULL.offset| 0) (<= 4 |~#drvlist~0.base|) (= |ULTIMATE.start_ldv_set_empty_#res#1| 0) (= |~#mutexes~0.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |ULTIMATE.start_ldv_set_empty_~s#1.offset|) (= |ULTIMATE.start_foo_~__mptr~5#1.offset| |~#drvlist~0.offset|) (<= 3 |~#mutexes~0.base|) (<= |ULTIMATE.start_foo_~me~0#1.offset| 0) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|)) (<= |#NULL.base| 0) (= |ULTIMATE.start_ldv_list_empty_#in~head#1.offset| |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (<= |~#drvlist~0.base| 4) (= |ULTIMATE.start_ldv_set_empty_~s#1.offset| |ULTIMATE.start_ldv_list_empty_#in~head#1.offset|) (= |~#drvlist~0.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_foo_~__mptr~5#1.base| |~#drvlist~0.base|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (<= 0 |#NULL.offset|) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= |~#mutexes~0.base| 3) (<= 1 |ULTIMATE.start_foo_~i~0#1|) (<= 0 |#StackHeapBarrier|) (= |ULTIMATE.start_foo_~__mptr~5#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (<= 0 |ULTIMATE.start_foo_~N~0#1|))' at error location [2021-11-25 19:09:01,870 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:09:01,871 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-25 19:09:01,871 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 12] total 32 [2021-11-25 19:09:01,871 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1069878071] [2021-11-25 19:09:01,871 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-25 19:09:01,872 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2021-11-25 19:09:01,872 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:09:01,873 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2021-11-25 19:09:01,874 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=199, Invalid=2057, Unknown=0, NotChecked=0, Total=2256 [2021-11-25 19:09:01,875 INFO L87 Difference]: Start difference. First operand 52 states and 64 transitions. Second operand has 32 states, 20 states have (on average 1.65) internal successors, (33), 25 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-11-25 19:09:03,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:09:03,590 INFO L93 Difference]: Finished difference Result 154 states and 196 transitions. [2021-11-25 19:09:03,591 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-11-25 19:09:03,594 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 20 states have (on average 1.65) internal successors, (33), 25 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 19 [2021-11-25 19:09:03,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:09:03,603 INFO L225 Difference]: With dead ends: 154 [2021-11-25 19:09:03,603 INFO L226 Difference]: Without dead ends: 136 [2021-11-25 19:09:03,607 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 804 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=441, Invalid=3719, Unknown=0, NotChecked=0, Total=4160 [2021-11-25 19:09:03,611 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 467 mSDsluCounter, 403 mSDsCounter, 0 mSdLazyCounter, 1068 mSolverCounterSat, 240 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 467 SdHoareTripleChecker+Valid, 429 SdHoareTripleChecker+Invalid, 1308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 240 IncrementalHoareTripleChecker+Valid, 1068 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2021-11-25 19:09:03,613 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [467 Valid, 429 Invalid, 1308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [240 Valid, 1068 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2021-11-25 19:09:03,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2021-11-25 19:09:03,644 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 92. [2021-11-25 19:09:03,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 65 states have (on average 1.3384615384615384) internal successors, (87), 70 states have internal predecessors, (87), 14 states have call successors, (14), 8 states have call predecessors, (14), 10 states have return successors, (20), 14 states have call predecessors, (20), 14 states have call successors, (20) [2021-11-25 19:09:03,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 121 transitions. [2021-11-25 19:09:03,657 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 121 transitions. Word has length 19 [2021-11-25 19:09:03,657 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:09:03,657 INFO L470 AbstractCegarLoop]: Abstraction has 92 states and 121 transitions. [2021-11-25 19:09:03,658 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 20 states have (on average 1.65) internal successors, (33), 25 states have internal predecessors, (33), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-11-25 19:09:03,658 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 121 transitions. [2021-11-25 19:09:03,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-11-25 19:09:03,659 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:09:03,660 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:09:03,691 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2021-11-25 19:09:03,880 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:03,881 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:09:03,881 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:09:03,881 INFO L85 PathProgramCache]: Analyzing trace with hash 983498160, now seen corresponding path program 1 times [2021-11-25 19:09:03,881 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:09:03,882 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1452662185] [2021-11-25 19:09:03,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:03,883 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:09:03,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:05,810 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:09:05,810 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:09:05,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1452662185] [2021-11-25 19:09:05,810 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1452662185] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:05,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [445442409] [2021-11-25 19:09:05,810 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:05,811 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:05,811 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:09:05,812 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:09:05,838 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-25 19:09:05,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:05,944 INFO L263 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 113 conjunts are in the unsatisfiable core [2021-11-25 19:09:05,951 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:09:06,241 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-11-25 19:09:06,241 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-11-25 19:09:06,391 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-11-25 19:09:06,402 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:06,807 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 33 [2021-11-25 19:09:06,838 INFO L354 Elim1Store]: treesize reduction 50, result has 29.6 percent of original size [2021-11-25 19:09:06,839 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 55 treesize of output 57 [2021-11-25 19:09:06,884 INFO L354 Elim1Store]: treesize reduction 24, result has 38.5 percent of original size [2021-11-25 19:09:06,885 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 61 treesize of output 64 [2021-11-25 19:09:06,899 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:06,899 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 50 treesize of output 42 [2021-11-25 19:09:06,921 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-11-25 19:09:06,922 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 32 [2021-11-25 19:09:06,934 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:07,244 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:09:07,245 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:09:07,768 WARN L838 $PredicateComparison]: unable to prove that (and (forall ((v_ArrVal_263 (Array Int Int)) (v___ldv_list_add_~next.offset_16 Int) (v_ArrVal_264 (Array Int Int))) (= |c_~#mutexes~0.base| (select (select (store (store (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (store |c_#memory_$Pointer$.base| .cse0 (store (select |c_#memory_$Pointer$.base| .cse0) (+ v___ldv_list_add_~next.offset_16 4) |c_ULTIMATE.start_foo_~me~0#1.base|))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_264) |c_~#drvlist~0.base| v_ArrVal_263) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|))) (forall ((v___ldv_list_add_~next.offset_16 Int) (v_ArrVal_265 (Array Int Int)) (v_ArrVal_266 (Array Int Int))) (= (select (select (store (store (let ((.cse1 (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (store |c_#memory_$Pointer$.offset| .cse1 (store (select |c_#memory_$Pointer$.offset| .cse1) (+ v___ldv_list_add_~next.offset_16 4) (+ 8 |c_ULTIMATE.start_foo_~me~0#1.offset|)))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_266) |c_~#drvlist~0.base| v_ArrVal_265) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.offset|))) is different from false [2021-11-25 19:09:07,770 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [445442409] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:07,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [45273345] [2021-11-25 19:09:07,774 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:09:07,774 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:09:07,775 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:09:07,775 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:09:07,775 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:09:07,829 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:09:07,834 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:09:08,140 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,222 INFO L354 Elim1Store]: treesize reduction 143, result has 32.9 percent of original size [2021-11-25 19:09:08,223 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 81 treesize of output 70 [2021-11-25 19:09:08,237 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,308 INFO L354 Elim1Store]: treesize reduction 159, result has 20.9 percent of original size [2021-11-25 19:09:08,308 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2021-11-25 19:09:08,320 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,411 INFO L354 Elim1Store]: treesize reduction 140, result has 30.3 percent of original size [2021-11-25 19:09:08,411 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2021-11-25 19:09:08,432 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:08,436 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:08,452 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:08,456 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:08,509 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,510 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,511 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:08,520 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,521 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,522 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:08,537 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:09:08,719 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,720 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,721 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:08,729 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,730 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:08,731 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:08,747 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:09:08,894 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:08,901 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:08,911 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:09:08,913 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:09:09,020 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:09,026 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:09,035 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:09:09,037 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:09:09,913 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 39 for LOIs [2021-11-25 19:09:09,920 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 51 for LOIs [2021-11-25 19:09:09,954 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 48 for LOIs [2021-11-25 19:09:10,019 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2021-11-25 19:09:10,051 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:09:14,812 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1445#(and (= |~#drvlist~0.offset| 0) (<= 0 (+ |ULTIMATE.start_foo_~N~0#1| 2147483648)) (= |~#mutexes~0.base| 3) (= |~#mutexes~0.offset| 0) (= |#NULL.offset| 0) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~i~0#1|) (= |#NULL.base| 0))' at error location [2021-11-25 19:09:14,812 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:09:14,813 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:09:14,813 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 27 [2021-11-25 19:09:14,813 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [376358402] [2021-11-25 19:09:14,813 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:09:14,813 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2021-11-25 19:09:14,814 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:09:14,814 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2021-11-25 19:09:14,815 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=216, Invalid=2216, Unknown=22, NotChecked=96, Total=2550 [2021-11-25 19:09:14,816 INFO L87 Difference]: Start difference. First operand 92 states and 121 transitions. Second operand has 27 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 20 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2021-11-25 19:09:16,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:09:16,930 INFO L93 Difference]: Finished difference Result 250 states and 338 transitions. [2021-11-25 19:09:16,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2021-11-25 19:09:16,931 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 20 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Word has length 25 [2021-11-25 19:09:16,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:09:16,933 INFO L225 Difference]: With dead ends: 250 [2021-11-25 19:09:16,933 INFO L226 Difference]: Without dead ends: 169 [2021-11-25 19:09:16,936 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 32 SyntacticMatches, 1 SemanticMatches, 70 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1510 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=488, Invalid=4456, Unknown=30, NotChecked=138, Total=5112 [2021-11-25 19:09:16,937 INFO L933 BasicCegarLoop]: 32 mSDtfsCounter, 162 mSDsluCounter, 338 mSDsCounter, 0 mSdLazyCounter, 804 mSolverCounterSat, 109 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 367 SdHoareTripleChecker+Invalid, 1058 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 109 IncrementalHoareTripleChecker+Valid, 804 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 145 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:09:16,937 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [163 Valid, 367 Invalid, 1058 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [109 Valid, 804 Invalid, 0 Unknown, 145 Unchecked, 1.0s Time] [2021-11-25 19:09:16,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2021-11-25 19:09:16,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 131. [2021-11-25 19:09:16,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 93 states have (on average 1.3333333333333333) internal successors, (124), 98 states have internal predecessors, (124), 20 states have call successors, (20), 12 states have call predecessors, (20), 15 states have return successors, (27), 21 states have call predecessors, (27), 20 states have call successors, (27) [2021-11-25 19:09:16,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 171 transitions. [2021-11-25 19:09:16,960 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 171 transitions. Word has length 25 [2021-11-25 19:09:16,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:09:16,960 INFO L470 AbstractCegarLoop]: Abstraction has 131 states and 171 transitions. [2021-11-25 19:09:16,961 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 18 states have (on average 1.7222222222222223) internal successors, (31), 20 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2021-11-25 19:09:16,961 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 171 transitions. [2021-11-25 19:09:16,964 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2021-11-25 19:09:16,965 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:09:16,965 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:09:16,988 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-11-25 19:09:17,168 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:17,169 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:09:17,169 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:09:17,169 INFO L85 PathProgramCache]: Analyzing trace with hash -487816988, now seen corresponding path program 2 times [2021-11-25 19:09:17,169 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:09:17,170 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [575777621] [2021-11-25 19:09:17,170 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:17,170 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:09:17,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:20,007 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-25 19:09:20,008 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:09:20,008 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [575777621] [2021-11-25 19:09:20,008 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [575777621] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:20,008 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [909878541] [2021-11-25 19:09:20,008 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-25 19:09:20,008 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:20,009 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:09:20,009 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:09:20,011 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-25 19:09:20,170 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-25 19:09:20,171 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:09:20,176 INFO L263 TraceCheckSpWp]: Trace formula consists of 453 conjuncts, 178 conjunts are in the unsatisfiable core [2021-11-25 19:09:20,184 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:09:20,475 INFO L354 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2021-11-25 19:09:20,476 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2021-11-25 19:09:20,624 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:20,635 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-11-25 19:09:21,116 INFO L354 Elim1Store]: treesize reduction 56, result has 13.8 percent of original size [2021-11-25 19:09:21,116 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 202 treesize of output 139 [2021-11-25 19:09:21,133 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:21,163 INFO L354 Elim1Store]: treesize reduction 45, result has 43.0 percent of original size [2021-11-25 19:09:21,163 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 3 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 5 new quantified variables, introduced 3 case distinctions, treesize of input 102 treesize of output 138 [2021-11-25 19:09:21,170 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 138 treesize of output 118 [2021-11-25 19:09:21,176 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 33 [2021-11-25 19:09:21,194 INFO L354 Elim1Store]: treesize reduction 9, result has 47.1 percent of original size [2021-11-25 19:09:21,194 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 128 treesize of output 111 [2021-11-25 19:09:21,210 INFO L354 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-11-25 19:09:21,210 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 28 treesize of output 36 [2021-11-25 19:09:21,222 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-11-25 19:09:21,238 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-11-25 19:09:21,289 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 46 [2021-11-25 19:09:21,332 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 20 [2021-11-25 19:09:21,337 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2021-11-25 19:09:21,372 INFO L354 Elim1Store]: treesize reduction 16, result has 5.9 percent of original size [2021-11-25 19:09:21,372 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 50 treesize of output 39 [2021-11-25 19:09:21,376 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 16 [2021-11-25 19:09:21,726 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-11-25 19:09:21,727 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-11-25 19:09:21,918 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:21,930 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2021-11-25 19:09:22,364 INFO L354 Elim1Store]: treesize reduction 53, result has 39.1 percent of original size [2021-11-25 19:09:22,364 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 24 treesize of output 49 [2021-11-25 19:09:22,391 INFO L354 Elim1Store]: treesize reduction 46, result has 35.2 percent of original size [2021-11-25 19:09:22,391 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 67 treesize of output 65 [2021-11-25 19:09:22,427 INFO L354 Elim1Store]: treesize reduction 47, result has 42.7 percent of original size [2021-11-25 19:09:22,428 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 89 treesize of output 108 [2021-11-25 19:09:22,740 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:22,823 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2021-11-25 19:09:23,122 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:09:23,122 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:09:23,527 WARN L838 $PredicateComparison]: unable to prove that (and (forall ((v_ArrVal_501 (Array Int Int)) (v___ldv_list_add_~next.offset_22 Int) (v_ArrVal_499 (Array Int Int))) (= (select (select (store (store (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (store |c_#memory_$Pointer$.base| .cse0 (store (select |c_#memory_$Pointer$.base| .cse0) (+ v___ldv_list_add_~next.offset_22 4) |c_ULTIMATE.start_foo_~me~0#1.base|))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_501) |c_~#drvlist~0.base| v_ArrVal_499) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.base|)) (forall ((v_ArrVal_502 (Array Int Int)) (v_ArrVal_503 (Array Int Int)) (v_ArrVal_500 (Array Int Int))) (= (select (select (store (store (store |c_#memory_$Pointer$.offset| (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|) v_ArrVal_503) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_500) |c_~#drvlist~0.base| v_ArrVal_502) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.offset|))) is different from false [2021-11-25 19:09:23,528 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [909878541] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:23,529 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [541696045] [2021-11-25 19:09:23,535 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:09:23,536 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:09:23,536 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:09:23,537 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:09:23,537 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:09:23,585 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:09:23,591 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:09:23,701 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:23,769 INFO L354 Elim1Store]: treesize reduction 140, result has 30.3 percent of original size [2021-11-25 19:09:23,769 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2021-11-25 19:09:23,794 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:23,890 INFO L354 Elim1Store]: treesize reduction 143, result has 32.9 percent of original size [2021-11-25 19:09:23,890 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 81 treesize of output 70 [2021-11-25 19:09:23,926 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:23,981 INFO L354 Elim1Store]: treesize reduction 159, result has 20.9 percent of original size [2021-11-25 19:09:23,982 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2021-11-25 19:09:24,013 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:24,017 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:24,027 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:24,030 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:24,048 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,051 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,051 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:24,057 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,057 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,058 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:24,109 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,110 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,111 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:24,120 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,121 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:24,122 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:24,163 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:24,169 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:24,194 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:24,205 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:25,191 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 39 for LOIs [2021-11-25 19:09:25,198 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 53 for LOIs [2021-11-25 19:09:25,227 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 48 for LOIs [2021-11-25 19:09:25,279 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2021-11-25 19:09:25,315 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:09:30,410 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2238#(and (= |~#drvlist~0.offset| 0) (<= 0 (+ |ULTIMATE.start_foo_~N~0#1| 2147483648)) (= |~#mutexes~0.base| 3) (= |~#mutexes~0.offset| 0) (= |#NULL.offset| 0) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~i~0#1|) (= |#NULL.base| 0))' at error location [2021-11-25 19:09:30,410 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:09:30,410 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:09:30,410 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 43 [2021-11-25 19:09:30,410 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [509553601] [2021-11-25 19:09:30,410 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:09:30,411 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 43 states [2021-11-25 19:09:30,411 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:09:30,411 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2021-11-25 19:09:30,413 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=335, Invalid=3910, Unknown=49, NotChecked=128, Total=4422 [2021-11-25 19:09:30,413 INFO L87 Difference]: Start difference. First operand 131 states and 171 transitions. Second operand has 43 states, 27 states have (on average 1.6296296296296295) internal successors, (44), 31 states have internal predecessors, (44), 13 states have call successors, (13), 9 states have call predecessors, (13), 14 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2021-11-25 19:09:33,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:09:33,975 INFO L93 Difference]: Finished difference Result 298 states and 397 transitions. [2021-11-25 19:09:33,976 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2021-11-25 19:09:33,976 INFO L78 Accepts]: Start accepts. Automaton has has 43 states, 27 states have (on average 1.6296296296296295) internal successors, (44), 31 states have internal predecessors, (44), 13 states have call successors, (13), 9 states have call predecessors, (13), 14 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) Word has length 38 [2021-11-25 19:09:33,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:09:33,979 INFO L225 Difference]: With dead ends: 298 [2021-11-25 19:09:33,979 INFO L226 Difference]: Without dead ends: 217 [2021-11-25 19:09:33,982 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 52 SyntacticMatches, 2 SemanticMatches, 92 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 3127 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=785, Invalid=7708, Unknown=67, NotChecked=182, Total=8742 [2021-11-25 19:09:33,983 INFO L933 BasicCegarLoop]: 30 mSDtfsCounter, 269 mSDsluCounter, 418 mSDsCounter, 0 mSdLazyCounter, 1233 mSolverCounterSat, 165 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 273 SdHoareTripleChecker+Valid, 444 SdHoareTripleChecker+Invalid, 1571 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 165 IncrementalHoareTripleChecker+Valid, 1233 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 173 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2021-11-25 19:09:33,983 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [273 Valid, 444 Invalid, 1571 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [165 Valid, 1233 Invalid, 0 Unknown, 173 Unchecked, 1.8s Time] [2021-11-25 19:09:33,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2021-11-25 19:09:34,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 170. [2021-11-25 19:09:34,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 120 states have (on average 1.3333333333333333) internal successors, (160), 127 states have internal predecessors, (160), 27 states have call successors, (27), 16 states have call predecessors, (27), 20 states have return successors, (35), 27 states have call predecessors, (35), 27 states have call successors, (35) [2021-11-25 19:09:34,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 222 transitions. [2021-11-25 19:09:34,009 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 222 transitions. Word has length 38 [2021-11-25 19:09:34,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:09:34,010 INFO L470 AbstractCegarLoop]: Abstraction has 170 states and 222 transitions. [2021-11-25 19:09:34,010 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 43 states, 27 states have (on average 1.6296296296296295) internal successors, (44), 31 states have internal predecessors, (44), 13 states have call successors, (13), 9 states have call predecessors, (13), 14 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2021-11-25 19:09:34,010 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 222 transitions. [2021-11-25 19:09:34,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2021-11-25 19:09:34,013 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:09:34,013 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:09:34,037 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-11-25 19:09:34,224 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:34,225 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:09:34,225 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:09:34,225 INFO L85 PathProgramCache]: Analyzing trace with hash -1497273319, now seen corresponding path program 1 times [2021-11-25 19:09:34,225 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:09:34,226 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1218243560] [2021-11-25 19:09:34,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:34,226 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:09:34,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:34,283 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2021-11-25 19:09:34,283 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:09:34,283 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1218243560] [2021-11-25 19:09:34,283 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1218243560] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:34,283 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1418096822] [2021-11-25 19:09:34,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:34,284 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:34,284 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:09:34,285 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:09:34,315 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-25 19:09:34,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:34,443 INFO L263 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 5 conjunts are in the unsatisfiable core [2021-11-25 19:09:34,445 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:09:34,502 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-25 19:09:34,502 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-11-25 19:09:34,503 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1418096822] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-25 19:09:34,503 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-11-25 19:09:34,503 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2021-11-25 19:09:34,503 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495667539] [2021-11-25 19:09:34,503 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-25 19:09:34,504 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-25 19:09:34,504 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:09:34,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-25 19:09:34,505 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-25 19:09:34,505 INFO L87 Difference]: Start difference. First operand 170 states and 222 transitions. Second operand has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:09:34,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:09:34,574 INFO L93 Difference]: Finished difference Result 316 states and 418 transitions. [2021-11-25 19:09:34,574 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-11-25 19:09:34,574 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2021-11-25 19:09:34,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:09:34,576 INFO L225 Difference]: With dead ends: 316 [2021-11-25 19:09:34,577 INFO L226 Difference]: Without dead ends: 184 [2021-11-25 19:09:34,577 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-11-25 19:09:34,578 INFO L933 BasicCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:09:34,579 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 117 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-25 19:09:34,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2021-11-25 19:09:34,601 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 180. [2021-11-25 19:09:34,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 180 states, 128 states have (on average 1.3125) internal successors, (168), 134 states have internal predecessors, (168), 27 states have call successors, (27), 16 states have call predecessors, (27), 22 states have return successors, (37), 30 states have call predecessors, (37), 27 states have call successors, (37) [2021-11-25 19:09:34,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 180 states to 180 states and 232 transitions. [2021-11-25 19:09:34,604 INFO L78 Accepts]: Start accepts. Automaton has 180 states and 232 transitions. Word has length 42 [2021-11-25 19:09:34,604 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:09:34,604 INFO L470 AbstractCegarLoop]: Abstraction has 180 states and 232 transitions. [2021-11-25 19:09:34,605 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2021-11-25 19:09:34,605 INFO L276 IsEmpty]: Start isEmpty. Operand 180 states and 232 transitions. [2021-11-25 19:09:34,607 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2021-11-25 19:09:34,607 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:09:34,607 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:09:34,633 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-25 19:09:34,820 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:34,821 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:09:34,821 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:09:34,822 INFO L85 PathProgramCache]: Analyzing trace with hash -1110778976, now seen corresponding path program 1 times [2021-11-25 19:09:34,822 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:09:34,822 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2090710270] [2021-11-25 19:09:34,822 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:34,822 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:09:34,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:35,543 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-11-25 19:09:35,543 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:09:35,543 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2090710270] [2021-11-25 19:09:35,544 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2090710270] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:35,544 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [597617199] [2021-11-25 19:09:35,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:35,544 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:35,544 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:09:35,545 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:09:35,545 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-25 19:09:35,672 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:35,675 INFO L263 TraceCheckSpWp]: Trace formula consists of 409 conjuncts, 51 conjunts are in the unsatisfiable core [2021-11-25 19:09:35,678 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:09:36,134 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-25 19:09:36,134 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:09:36,548 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 16 [2021-11-25 19:09:36,595 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-11-25 19:09:36,596 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [597617199] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-25 19:09:36,596 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1879261009] [2021-11-25 19:09:36,599 INFO L159 IcfgInterpreter]: Started Sifa with 34 locations of interest [2021-11-25 19:09:36,599 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:09:36,600 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:09:36,600 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:09:36,600 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:09:36,651 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:09:36,662 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:09:36,815 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:36,896 INFO L354 Elim1Store]: treesize reduction 143, result has 32.9 percent of original size [2021-11-25 19:09:36,897 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 81 treesize of output 70 [2021-11-25 19:09:36,909 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:36,981 INFO L354 Elim1Store]: treesize reduction 140, result has 30.3 percent of original size [2021-11-25 19:09:36,982 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2021-11-25 19:09:36,993 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,055 INFO L354 Elim1Store]: treesize reduction 159, result has 20.9 percent of original size [2021-11-25 19:09:37,055 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2021-11-25 19:09:37,078 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:37,084 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:37,107 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:37,112 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:37,149 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,150 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,152 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,160 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,161 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,162 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,198 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,199 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,200 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,206 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,207 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,208 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,246 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,257 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,296 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,304 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,518 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,519 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,520 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,533 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,534 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,535 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,711 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,712 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,713 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,722 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,723 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:37,724 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:37,951 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,957 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,967 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:37,973 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:38,141 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:38,149 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:38,158 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:38,168 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:40,261 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 39 for LOIs [2021-11-25 19:09:40,267 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 24 for LOIs [2021-11-25 19:09:40,299 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 48 for LOIs [2021-11-25 19:09:40,347 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2021-11-25 19:09:40,378 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:09:46,083 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4079#(and (<= 0 (+ |ULTIMATE.start_foo_~N~0#1| 2147483648)) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (or (and (= |~#drvlist~0.offset| 0) (= |ULTIMATE.start_foo_~__mptr~7#1.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_mutex_unlock_#in~m#1.base| |ULTIMATE.start_mutex_unlock_~m#1.base|) (= (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|) |ULTIMATE.start_foo_~__mptr~7#1.base|) (= |~#mutexes~0.base| 3) (= |ULTIMATE.start_mutex_unlock_#in~m#1.offset| |ULTIMATE.start_mutex_unlock_~m#1.offset|) (= |~#mutexes~0.offset| 0) (not (= (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|)) (= |#NULL.offset| 0) (= |ULTIMATE.start_mutex_unlock_#in~m#1.base| |ULTIMATE.start_foo_~me~1#1.base|) (= 4 |~#drvlist~0.base|) (= |ULTIMATE.start_mutex_unlock_#in~m#1.offset| |ULTIMATE.start_foo_~me~1#1.offset|) (= |#NULL.base| 0)) (and (= |~#drvlist~0.offset| 0) (= |ULTIMATE.start_foo_~__mptr~7#1.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_mutex_unlock_#in~m#1.base| |ULTIMATE.start_mutex_unlock_~m#1.base|) (= (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|) |ULTIMATE.start_foo_~__mptr~7#1.base|) (= |~#mutexes~0.base| 3) (= |ULTIMATE.start_mutex_unlock_#in~m#1.offset| |ULTIMATE.start_mutex_unlock_~m#1.offset|) (= |~#mutexes~0.offset| 0) (not (= |~#drvlist~0.base| |ULTIMATE.start_foo_~me~1#1.base|)) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|)) (= |#NULL.offset| 0) (= |ULTIMATE.start_mutex_unlock_#in~m#1.base| |ULTIMATE.start_foo_~me~1#1.base|) (= 4 |~#drvlist~0.base|) (= |ULTIMATE.start_mutex_unlock_#in~m#1.offset| |ULTIMATE.start_foo_~me~1#1.offset|) (= |#NULL.base| 0))) (<= 0 |#StackHeapBarrier|) (<= 0 |ULTIMATE.start_foo_~i~0#1|))' at error location [2021-11-25 19:09:46,083 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:09:46,083 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-25 19:09:46,083 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 9, 8] total 33 [2021-11-25 19:09:46,083 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [309143894] [2021-11-25 19:09:46,083 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-25 19:09:46,085 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2021-11-25 19:09:46,085 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:09:46,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2021-11-25 19:09:46,087 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=237, Invalid=2843, Unknown=0, NotChecked=0, Total=3080 [2021-11-25 19:09:46,087 INFO L87 Difference]: Start difference. First operand 180 states and 232 transitions. Second operand has 33 states, 26 states have (on average 2.8461538461538463) internal successors, (74), 28 states have internal predecessors, (74), 10 states have call successors, (17), 7 states have call predecessors, (17), 12 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2021-11-25 19:09:48,766 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:09:48,767 INFO L93 Difference]: Finished difference Result 397 states and 519 transitions. [2021-11-25 19:09:48,767 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2021-11-25 19:09:48,768 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 26 states have (on average 2.8461538461538463) internal successors, (74), 28 states have internal predecessors, (74), 10 states have call successors, (17), 7 states have call predecessors, (17), 12 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) Word has length 43 [2021-11-25 19:09:48,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:09:48,771 INFO L225 Difference]: With dead ends: 397 [2021-11-25 19:09:48,771 INFO L226 Difference]: Without dead ends: 237 [2021-11-25 19:09:48,775 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 98 SyntacticMatches, 4 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2032 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=748, Invalid=6734, Unknown=0, NotChecked=0, Total=7482 [2021-11-25 19:09:48,776 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 314 mSDsluCounter, 354 mSDsCounter, 0 mSdLazyCounter, 892 mSolverCounterSat, 220 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 326 SdHoareTripleChecker+Valid, 384 SdHoareTripleChecker+Invalid, 1112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 220 IncrementalHoareTripleChecker+Valid, 892 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2021-11-25 19:09:48,776 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [326 Valid, 384 Invalid, 1112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [220 Valid, 892 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2021-11-25 19:09:48,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2021-11-25 19:09:48,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 170. [2021-11-25 19:09:48,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 119 states have (on average 1.2773109243697478) internal successors, (152), 125 states have internal predecessors, (152), 25 states have call successors, (25), 18 states have call predecessors, (25), 23 states have return successors, (38), 27 states have call predecessors, (38), 25 states have call successors, (38) [2021-11-25 19:09:48,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 215 transitions. [2021-11-25 19:09:48,803 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 215 transitions. Word has length 43 [2021-11-25 19:09:48,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:09:48,804 INFO L470 AbstractCegarLoop]: Abstraction has 170 states and 215 transitions. [2021-11-25 19:09:48,804 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 26 states have (on average 2.8461538461538463) internal successors, (74), 28 states have internal predecessors, (74), 10 states have call successors, (17), 7 states have call predecessors, (17), 12 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2021-11-25 19:09:48,804 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 215 transitions. [2021-11-25 19:09:48,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2021-11-25 19:09:48,806 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:09:48,806 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:09:48,850 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-11-25 19:09:49,020 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:49,021 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:09:49,021 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:09:49,021 INFO L85 PathProgramCache]: Analyzing trace with hash -779276848, now seen corresponding path program 1 times [2021-11-25 19:09:49,021 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:09:49,021 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1059736473] [2021-11-25 19:09:49,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:49,022 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:09:49,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:51,732 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-11-25 19:09:51,732 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:09:51,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1059736473] [2021-11-25 19:09:51,733 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1059736473] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:51,733 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [134278949] [2021-11-25 19:09:51,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:09:51,733 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:09:51,733 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:09:51,740 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:09:51,741 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-25 19:09:51,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:09:51,932 INFO L263 TraceCheckSpWp]: Trace formula consists of 565 conjuncts, 152 conjunts are in the unsatisfiable core [2021-11-25 19:09:51,941 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:09:52,155 INFO L354 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2021-11-25 19:09:52,155 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2021-11-25 19:09:52,268 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:52,504 INFO L354 Elim1Store]: treesize reduction 117, result has 35.4 percent of original size [2021-11-25 19:09:52,505 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 92 treesize of output 130 [2021-11-25 19:09:52,511 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:09:52,527 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:09:52,538 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:09:52,605 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:52,606 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 31 [2021-11-25 19:09:52,614 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:52,629 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:52,692 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2021-11-25 19:09:52,698 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:52,776 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2021-11-25 19:09:52,780 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:52,858 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:52,861 INFO L354 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2021-11-25 19:09:52,862 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 22 treesize of output 16 [2021-11-25 19:09:52,870 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:52,932 INFO L354 Elim1Store]: treesize reduction 9, result has 47.1 percent of original size [2021-11-25 19:09:52,935 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 49 treesize of output 49 [2021-11-25 19:09:52,947 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:52,983 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:53,004 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:53,203 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:53,699 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-11-25 19:09:53,699 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-11-25 19:09:53,777 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2021-11-25 19:09:53,844 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:53,976 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 19 [2021-11-25 19:09:54,008 INFO L354 Elim1Store]: treesize reduction 33, result has 40.0 percent of original size [2021-11-25 19:09:54,009 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 34 [2021-11-25 19:09:54,137 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:54,147 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:54,911 INFO L354 Elim1Store]: treesize reduction 19, result has 47.2 percent of original size [2021-11-25 19:09:54,911 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 39 [2021-11-25 19:09:54,918 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:54,940 INFO L354 Elim1Store]: treesize reduction 41, result has 34.9 percent of original size [2021-11-25 19:09:54,940 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 36 treesize of output 54 [2021-11-25 19:09:55,057 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:57,378 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:57,379 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 52 treesize of output 52 [2021-11-25 19:09:57,389 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:57,389 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 31 [2021-11-25 19:09:57,522 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:09:57,522 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:09:57,861 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:57,862 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 25 [2021-11-25 19:09:57,882 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:57,883 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 133 treesize of output 132 [2021-11-25 19:09:57,894 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 114 treesize of output 110 [2021-11-25 19:09:57,902 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 110 treesize of output 102 [2021-11-25 19:09:58,061 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2021-11-25 19:09:58,167 WARN L838 $PredicateComparison]: unable to prove that (forall ((v___ldv_list_add_~prev.base_31 Int) (v_ArrVal_908 (Array Int Int)) (v_ArrVal_907 (Array Int Int)) (v___ldv_list_add_~next.base_33 Int) (v___ldv_list_add_~next.offset_34 Int)) (let ((.cse0 (+ v___ldv_list_add_~next.offset_34 4))) (or (< |c_ULTIMATE.start_ldv_set_add_~s#1.base| v___ldv_list_add_~prev.base_31) (not (= |c_~#drvlist~0.offset| (select (select (store (store (store |c_#memory_$Pointer$.offset| v___ldv_list_add_~next.base_33 (store (select |c_#memory_$Pointer$.offset| v___ldv_list_add_~next.base_33) .cse0 (+ |c_ULTIMATE.start_ldv_set_add_~le~0#1.offset| 4))) |c_ULTIMATE.start_ldv_set_add_~le~0#1.base| v_ArrVal_908) v___ldv_list_add_~prev.base_31 v_ArrVal_907) |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (and (= v___ldv_list_add_~next.base_33 |c_~#drvlist~0.base|) (= .cse0 |c_~#drvlist~0.offset|) (not (= |c_ULTIMATE.start_ldv_set_add_~le~0#1.base| |c_~#drvlist~0.base|)) (not (= |c_~#drvlist~0.base| v___ldv_list_add_~prev.base_31)))))) is different from false [2021-11-25 19:09:58,169 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [134278949] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:09:58,169 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1616513945] [2021-11-25 19:09:58,172 INFO L159 IcfgInterpreter]: Started Sifa with 34 locations of interest [2021-11-25 19:09:58,172 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:09:58,173 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:09:58,173 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:09:58,173 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:09:58,226 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:09:58,231 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:09:58,341 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,412 INFO L354 Elim1Store]: treesize reduction 143, result has 32.9 percent of original size [2021-11-25 19:09:58,412 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 81 treesize of output 70 [2021-11-25 19:09:58,423 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,476 INFO L354 Elim1Store]: treesize reduction 159, result has 20.9 percent of original size [2021-11-25 19:09:58,477 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2021-11-25 19:09:58,487 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,561 INFO L354 Elim1Store]: treesize reduction 140, result has 30.3 percent of original size [2021-11-25 19:09:58,562 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2021-11-25 19:09:58,583 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:58,599 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:58,612 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:58,617 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:09:58,642 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,643 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,644 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:58,652 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,653 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,654 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:58,689 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,690 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,691 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:58,698 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,699 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:09:58,700 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:09:58,744 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:58,752 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:58,783 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:58,790 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:09:59,718 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:09:59,729 INFO L354 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2021-11-25 19:09:59,729 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 22 [2021-11-25 19:09:59,739 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2021-11-25 19:09:59,750 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:09:59,761 INFO L354 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2021-11-25 19:09:59,761 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 22 [2021-11-25 19:09:59,830 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:09:59,836 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:59,836 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 19 [2021-11-25 19:09:59,847 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:09:59,852 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:59,853 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 19 [2021-11-25 19:09:59,913 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:09:59,918 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:59,919 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 19 [2021-11-25 19:09:59,929 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:09:59,934 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:09:59,935 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 19 [2021-11-25 19:10:00,287 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2021-11-25 19:10:00,299 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:10:00,311 INFO L354 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2021-11-25 19:10:00,312 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 192 treesize of output 191 [2021-11-25 19:10:00,319 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:10:00,330 INFO L354 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2021-11-25 19:10:00,331 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 184 treesize of output 183 [2021-11-25 19:10:00,544 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:10:00,550 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:10:00,551 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 204 treesize of output 200 [2021-11-25 19:10:00,559 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:10:00,566 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:10:00,566 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 196 treesize of output 192 [2021-11-25 19:10:00,822 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:10:00,829 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:10:00,830 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 204 treesize of output 200 [2021-11-25 19:10:00,842 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-25 19:10:00,850 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:10:00,851 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 196 treesize of output 192 [2021-11-25 19:10:01,889 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 39 for LOIs [2021-11-25 19:10:01,905 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:10:01,917 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:10:01,919 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 41 for LOIs [2021-11-25 19:10:01,938 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 44 for LOIs [2021-11-25 19:10:01,985 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:10:01,992 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:10:02,028 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:10:02,033 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:10:02,072 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 61 for LOIs [2021-11-25 19:10:02,123 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:10:13,346 WARN L227 SmtUtils]: Spent 5.27s on a formula simplification. DAG size of input: 112 DAG size of output: 100 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2021-11-25 19:10:17,561 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '5167#(and (= (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|) |~#drvlist~0.offset|) (= |~#drvlist~0.offset| 0) (<= 0 (+ |ULTIMATE.start_foo_~N~0#1| 2147483648)) (= |ULTIMATE.start_foo_~__mptr~7#1.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |~#mutexes~0.offset|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (select (select |#memory_$Pointer$.offset| |~#drvlist~0.base|) |~#drvlist~0.offset|)) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_ldv_list_empty_#res#1| |ULTIMATE.start_ldv_set_empty_#res#1|) (= (select (select |#memory_$Pointer$.base| |~#drvlist~0.base|) |~#drvlist~0.offset|) |ULTIMATE.start_foo_~__mptr~7#1.base|) (= |~#mutexes~0.base| 3) (= (ite (and (= (select (select |#memory_$Pointer$.offset| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (= |ULTIMATE.start_ldv_list_empty_~head#1.base| (select (select |#memory_$Pointer$.base| |ULTIMATE.start_ldv_list_empty_~head#1.base|) |ULTIMATE.start_ldv_list_empty_~head#1.offset|))) 1 0) |ULTIMATE.start_ldv_list_empty_#res#1|) (= |ULTIMATE.start_ldv_set_empty_#res#1| 0) (= |~#mutexes~0.offset| 0) (= |~#mutexes~0.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (= |ULTIMATE.start_ldv_set_empty_#in~s#1.offset| |ULTIMATE.start_ldv_set_empty_~s#1.offset|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_list_empty_#in~head#1.base|) (= |ULTIMATE.start_foo_~__mptr~7#1.offset| (+ 8 |ULTIMATE.start_foo_~me~1#1.offset|)) (= |ULTIMATE.start_ldv_list_empty_#in~head#1.offset| |ULTIMATE.start_ldv_list_empty_~head#1.offset|) (= |#NULL.offset| 0) (= |ULTIMATE.start_ldv_set_empty_~s#1.offset| |ULTIMATE.start_ldv_list_empty_#in~head#1.offset|) (= |~#drvlist~0.base| |ULTIMATE.start_foo_~me~1#1.base|) (= |ULTIMATE.start_ldv_set_empty_~s#1.base| |ULTIMATE.start_ldv_set_empty_#in~s#1.base|) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~i~0#1|) (= |#NULL.base| 0))' at error location [2021-11-25 19:10:17,561 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:10:17,561 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:10:17,561 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 24] total 50 [2021-11-25 19:10:17,562 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1811207983] [2021-11-25 19:10:17,562 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:10:17,562 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2021-11-25 19:10:17,562 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:10:17,563 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2021-11-25 19:10:17,565 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=280, Invalid=5629, Unknown=101, NotChecked=152, Total=6162 [2021-11-25 19:10:17,566 INFO L87 Difference]: Start difference. First operand 170 states and 215 transitions. Second operand has 50 states, 33 states have (on average 1.8181818181818181) internal successors, (60), 38 states have internal predecessors, (60), 14 states have call successors, (16), 10 states have call predecessors, (16), 16 states have return successors, (16), 15 states have call predecessors, (16), 14 states have call successors, (16) [2021-11-25 19:11:04,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:11:04,097 INFO L93 Difference]: Finished difference Result 394 states and 508 transitions. [2021-11-25 19:11:04,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2021-11-25 19:11:04,099 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 33 states have (on average 1.8181818181818181) internal successors, (60), 38 states have internal predecessors, (60), 14 states have call successors, (16), 10 states have call predecessors, (16), 16 states have return successors, (16), 15 states have call predecessors, (16), 14 states have call successors, (16) Word has length 47 [2021-11-25 19:11:04,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:11:04,103 INFO L225 Difference]: With dead ends: 394 [2021-11-25 19:11:04,103 INFO L226 Difference]: Without dead ends: 391 [2021-11-25 19:11:04,111 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 212 GetRequests, 61 SyntacticMatches, 4 SemanticMatches, 147 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 6470 ImplicationChecksByTransitivity, 63.9s TimeCoverageRelationStatistics Valid=1350, Invalid=20247, Unknown=163, NotChecked=292, Total=22052 [2021-11-25 19:11:04,112 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 351 mSDsluCounter, 806 mSDsCounter, 0 mSdLazyCounter, 2110 mSolverCounterSat, 330 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 364 SdHoareTripleChecker+Valid, 837 SdHoareTripleChecker+Invalid, 2959 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 330 IncrementalHoareTripleChecker+Valid, 2110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 519 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2021-11-25 19:11:04,112 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [364 Valid, 837 Invalid, 2959 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [330 Valid, 2110 Invalid, 0 Unknown, 519 Unchecked, 2.6s Time] [2021-11-25 19:11:04,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 391 states. [2021-11-25 19:11:04,168 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 391 to 298. [2021-11-25 19:11:04,170 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 298 states, 207 states have (on average 1.2608695652173914) internal successors, (261), 221 states have internal predecessors, (261), 43 states have call successors, (43), 32 states have call predecessors, (43), 45 states have return successors, (74), 45 states have call predecessors, (74), 43 states have call successors, (74) [2021-11-25 19:11:04,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 298 states to 298 states and 378 transitions. [2021-11-25 19:11:04,175 INFO L78 Accepts]: Start accepts. Automaton has 298 states and 378 transitions. Word has length 47 [2021-11-25 19:11:04,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:11:04,176 INFO L470 AbstractCegarLoop]: Abstraction has 298 states and 378 transitions. [2021-11-25 19:11:04,176 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 33 states have (on average 1.8181818181818181) internal successors, (60), 38 states have internal predecessors, (60), 14 states have call successors, (16), 10 states have call predecessors, (16), 16 states have return successors, (16), 15 states have call predecessors, (16), 14 states have call successors, (16) [2021-11-25 19:11:04,177 INFO L276 IsEmpty]: Start isEmpty. Operand 298 states and 378 transitions. [2021-11-25 19:11:04,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2021-11-25 19:11:04,184 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:11:04,185 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:11:04,219 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-11-25 19:11:04,399 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2021-11-25 19:11:04,399 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:11:04,399 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:11:04,399 INFO L85 PathProgramCache]: Analyzing trace with hash 1056494128, now seen corresponding path program 3 times [2021-11-25 19:11:04,400 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:11:04,400 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2053834668] [2021-11-25 19:11:04,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:11:04,400 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:11:04,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:11:07,969 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 19 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2021-11-25 19:11:07,969 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:11:07,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2053834668] [2021-11-25 19:11:07,969 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2053834668] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:11:07,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [140244407] [2021-11-25 19:11:07,969 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-25 19:11:07,969 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:11:07,969 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:11:07,970 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:11:07,971 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-11-25 19:11:09,486 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-25 19:11:09,486 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-25 19:11:09,494 INFO L263 TraceCheckSpWp]: Trace formula consists of 620 conjuncts, 263 conjunts are in the unsatisfiable core [2021-11-25 19:11:09,501 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:11:09,803 INFO L354 Elim1Store]: treesize reduction 36, result has 34.5 percent of original size [2021-11-25 19:11:09,804 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 22 treesize of output 33 [2021-11-25 19:11:09,986 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-11-25 19:11:10,005 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:10,751 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:10,774 INFO L354 Elim1Store]: treesize reduction 104, result has 9.6 percent of original size [2021-11-25 19:11:10,774 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 89 treesize of output 86 [2021-11-25 19:11:10,781 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 39 [2021-11-25 19:11:10,788 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 25 [2021-11-25 19:11:10,794 INFO L354 Elim1Store]: treesize reduction 16, result has 5.9 percent of original size [2021-11-25 19:11:10,795 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 60 treesize of output 47 [2021-11-25 19:11:10,799 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 22 [2021-11-25 19:11:10,804 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:11:11,056 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 10 [2021-11-25 19:11:11,306 INFO L354 Elim1Store]: treesize reduction 66, result has 35.3 percent of original size [2021-11-25 19:11:11,306 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 31 treesize of output 53 [2021-11-25 19:11:11,555 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:11,570 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 21 [2021-11-25 19:11:12,637 INFO L354 Elim1Store]: treesize reduction 56, result has 21.1 percent of original size [2021-11-25 19:11:12,637 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 121 treesize of output 83 [2021-11-25 19:11:12,694 INFO L354 Elim1Store]: treesize reduction 160, result has 16.2 percent of original size [2021-11-25 19:11:12,695 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 7 new quantified variables, introduced 8 case distinctions, treesize of input 227 treesize of output 177 [2021-11-25 19:11:12,701 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 200 treesize of output 161 [2021-11-25 19:11:12,709 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 35 [2021-11-25 19:11:12,722 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 39 [2021-11-25 19:11:12,731 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2021-11-25 19:11:12,741 WARN L220 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:11:12,809 INFO L354 Elim1Store]: treesize reduction 24, result has 4.0 percent of original size [2021-11-25 19:11:12,810 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 3 case distinctions, treesize of input 101 treesize of output 80 [2021-11-25 19:11:12,815 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 9 [2021-11-25 19:11:13,235 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 13 [2021-11-25 19:11:13,683 INFO L354 Elim1Store]: treesize reduction 16, result has 59.0 percent of original size [2021-11-25 19:11:13,684 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 6 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 32 treesize of output 38 [2021-11-25 19:11:14,169 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 19 [2021-11-25 19:11:14,174 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 7 [2021-11-25 19:11:14,806 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:14,807 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:14,808 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 45 [2021-11-25 19:11:14,891 INFO L354 Elim1Store]: treesize reduction 90, result has 21.1 percent of original size [2021-11-25 19:11:14,892 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 3 case distinctions, treesize of input 101 treesize of output 76 [2021-11-25 19:11:14,934 INFO L354 Elim1Store]: treesize reduction 96, result has 17.9 percent of original size [2021-11-25 19:11:14,934 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 7 case distinctions, treesize of input 178 treesize of output 140 [2021-11-25 19:11:14,942 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 53 treesize of output 63 [2021-11-25 19:11:14,949 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 9 [2021-11-25 19:11:16,385 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 7 proven. 32 refuted. 3 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-25 19:11:16,385 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-25 19:11:16,923 WARN L838 $PredicateComparison]: unable to prove that (and (forall ((v_ArrVal_1242 (Array Int Int)) (v_ArrVal_1241 (Array Int Int)) (v___ldv_list_add_~next.offset_42 Int)) (= |c_~#mutexes~0.base| (select (select (store (store (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (store |c_#memory_$Pointer$.base| .cse0 (store (select |c_#memory_$Pointer$.base| .cse0) (+ v___ldv_list_add_~next.offset_42 4) |c_ULTIMATE.start_foo_~me~0#1.base|))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_1241) |c_~#drvlist~0.base| v_ArrVal_1242) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|))) (forall ((v_ArrVal_1243 (Array Int Int)) (v_ArrVal_1240 (Array Int Int)) (v___ldv_list_add_~next.offset_42 Int)) (= (select (select (store (store (let ((.cse1 (select (select |c_#memory_$Pointer$.base| |c_~#drvlist~0.base|) |c_~#drvlist~0.offset|))) (store |c_#memory_$Pointer$.offset| .cse1 (store (select |c_#memory_$Pointer$.offset| .cse1) (+ v___ldv_list_add_~next.offset_42 4) (+ 8 |c_ULTIMATE.start_foo_~me~0#1.offset|)))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_1240) |c_~#drvlist~0.base| v_ArrVal_1243) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.offset|))) is different from false [2021-11-25 19:11:16,925 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [140244407] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:11:16,925 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2124333501] [2021-11-25 19:11:16,927 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2021-11-25 19:11:16,927 INFO L166 IcfgInterpreter]: Building call graph [2021-11-25 19:11:16,927 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-25 19:11:16,927 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-25 19:11:16,927 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-25 19:11:16,974 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-11-25 19:11:16,979 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 9 [2021-11-25 19:11:17,085 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,156 INFO L354 Elim1Store]: treesize reduction 140, result has 30.3 percent of original size [2021-11-25 19:11:17,156 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 68 [2021-11-25 19:11:17,208 INFO L354 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2021-11-25 19:11:17,208 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 19 [2021-11-25 19:11:17,234 INFO L354 Elim1Store]: treesize reduction 33, result has 34.0 percent of original size [2021-11-25 19:11:17,235 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 39 treesize of output 31 [2021-11-25 19:11:17,257 INFO L354 Elim1Store]: treesize reduction 25, result has 43.2 percent of original size [2021-11-25 19:11:17,257 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 31 [2021-11-25 19:11:17,271 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,327 INFO L354 Elim1Store]: treesize reduction 159, result has 20.9 percent of original size [2021-11-25 19:11:17,327 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 77 treesize of output 49 [2021-11-25 19:11:17,348 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:17,352 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:17,363 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:17,366 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:17,382 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,383 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,383 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,392 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,393 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,393 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,419 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,420 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,420 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,427 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,428 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,428 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,463 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:17,469 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:17,491 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:17,498 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:17,629 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,630 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,631 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,638 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,639 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,639 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,832 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,833 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,833 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:17,842 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,842 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:17,843 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-11-25 19:11:18,030 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,036 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,047 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,053 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,178 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,207 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,221 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:18,230 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2021-11-25 19:11:19,200 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 27 for LOIs [2021-11-25 19:11:19,205 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 90 for LOIs [2021-11-25 19:11:19,274 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_list_add with input of size 34 for LOIs [2021-11-25 19:11:19,318 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 42 for LOIs [2021-11-25 19:11:19,377 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-25 19:11:26,204 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '6551#(and (= |~#drvlist~0.offset| 0) (= |~#mutexes~0.base| 3) (= |ULTIMATE.start_foo_~me~0#1.offset| 0) (= |~#mutexes~0.offset| 0) (= |#NULL.offset| 0) (<= |ULTIMATE.start_foo_~N~0#1| 2147483647) (<= 1 |ULTIMATE.start_foo_~i~0#1|) (<= 0 |#StackHeapBarrier|) (= 4 |~#drvlist~0.base|) (<= 0 |ULTIMATE.start_foo_~N~0#1|) (= |#NULL.base| 0))' at error location [2021-11-25 19:11:26,204 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-25 19:11:26,205 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-11-25 19:11:26,205 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 31] total 51 [2021-11-25 19:11:26,205 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1826624911] [2021-11-25 19:11:26,205 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-11-25 19:11:26,206 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2021-11-25 19:11:26,206 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-25 19:11:26,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2021-11-25 19:11:26,207 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=365, Invalid=4953, Unknown=88, NotChecked=144, Total=5550 [2021-11-25 19:11:26,208 INFO L87 Difference]: Start difference. First operand 298 states and 378 transitions. Second operand has 51 states, 31 states have (on average 1.6451612903225807) internal successors, (51), 36 states have internal predecessors, (51), 15 states have call successors, (16), 11 states have call predecessors, (16), 17 states have return successors, (17), 16 states have call predecessors, (17), 15 states have call successors, (17) [2021-11-25 19:11:37,593 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-25 19:11:37,594 INFO L93 Difference]: Finished difference Result 517 states and 664 transitions. [2021-11-25 19:11:37,594 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2021-11-25 19:11:37,595 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 31 states have (on average 1.6451612903225807) internal successors, (51), 36 states have internal predecessors, (51), 15 states have call successors, (16), 11 states have call predecessors, (16), 17 states have return successors, (17), 16 states have call predecessors, (17), 15 states have call successors, (17) Word has length 51 [2021-11-25 19:11:37,595 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-25 19:11:37,598 INFO L225 Difference]: With dead ends: 517 [2021-11-25 19:11:37,598 INFO L226 Difference]: Without dead ends: 343 [2021-11-25 19:11:37,601 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 182 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 98 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 3294 ImplicationChecksByTransitivity, 21.8s TimeCoverageRelationStatistics Valid=678, Invalid=8901, Unknown=127, NotChecked=194, Total=9900 [2021-11-25 19:11:37,602 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 45 mSDsluCounter, 452 mSDsCounter, 0 mSdLazyCounter, 589 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 479 SdHoareTripleChecker+Invalid, 1351 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 589 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 687 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2021-11-25 19:11:37,602 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [47 Valid, 479 Invalid, 1351 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 589 Invalid, 0 Unknown, 687 Unchecked, 0.8s Time] [2021-11-25 19:11:37,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2021-11-25 19:11:37,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 313. [2021-11-25 19:11:37,646 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 313 states, 217 states have (on average 1.262672811059908) internal successors, (274), 233 states have internal predecessors, (274), 43 states have call successors, (43), 35 states have call predecessors, (43), 50 states have return successors, (76), 45 states have call predecessors, (76), 43 states have call successors, (76) [2021-11-25 19:11:37,649 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 313 states to 313 states and 393 transitions. [2021-11-25 19:11:37,649 INFO L78 Accepts]: Start accepts. Automaton has 313 states and 393 transitions. Word has length 51 [2021-11-25 19:11:37,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-25 19:11:37,650 INFO L470 AbstractCegarLoop]: Abstraction has 313 states and 393 transitions. [2021-11-25 19:11:37,650 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 31 states have (on average 1.6451612903225807) internal successors, (51), 36 states have internal predecessors, (51), 15 states have call successors, (16), 11 states have call predecessors, (16), 17 states have return successors, (17), 16 states have call predecessors, (17), 15 states have call successors, (17) [2021-11-25 19:11:37,650 INFO L276 IsEmpty]: Start isEmpty. Operand 313 states and 393 transitions. [2021-11-25 19:11:37,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2021-11-25 19:11:37,651 INFO L506 BasicCegarLoop]: Found error trace [2021-11-25 19:11:37,651 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-11-25 19:11:37,676 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-11-25 19:11:37,852 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-11-25 19:11:37,853 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-25 19:11:37,853 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-25 19:11:37,853 INFO L85 PathProgramCache]: Analyzing trace with hash -780762879, now seen corresponding path program 1 times [2021-11-25 19:11:37,853 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-25 19:11:37,854 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1364989644] [2021-11-25 19:11:37,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:11:37,854 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-25 19:11:37,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:11:41,598 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-11-25 19:11:41,599 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-25 19:11:41,599 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1364989644] [2021-11-25 19:11:41,599 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1364989644] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-25 19:11:41,599 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1934505296] [2021-11-25 19:11:41,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-25 19:11:41,599 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-25 19:11:41,599 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 [2021-11-25 19:11:41,602 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-25 19:11:41,602 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_9a2fa951-936f-45b8-8ee9-d529aa09af05/bin/utaipan-eEHZpOm5b7/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-11-25 19:11:41,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-25 19:11:41,829 INFO L263 TraceCheckSpWp]: Trace formula consists of 634 conjuncts, 249 conjunts are in the unsatisfiable core [2021-11-25 19:11:41,835 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-25 19:11:42,153 INFO L354 Elim1Store]: treesize reduction 36, result has 34.5 percent of original size [2021-11-25 19:11:42,154 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 22 treesize of output 33 [2021-11-25 19:11:42,389 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-11-25 19:11:42,401 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:42,935 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-25 19:11:42,957 INFO L354 Elim1Store]: treesize reduction 56, result has 13.8 percent of original size [2021-11-25 19:11:42,957 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 111 treesize of output 86 [2021-11-25 19:11:42,988 INFO L354 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2021-11-25 19:11:42,989 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 70 treesize of output 75 [2021-11-25 19:11:42,996 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 23 [2021-11-25 19:11:43,000 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 34 [2021-11-25 19:11:43,019 INFO L354 Elim1Store]: treesize reduction 35, result has 23.9 percent of original size [2021-11-25 19:11:43,019 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 75 treesize of output 70 [2021-11-25 19:11:43,027 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-25 19:11:43,028 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 48 treesize of output 40 [2021-11-25 19:11:43,033 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2021-11-25 19:11:43,426 INFO L354 Elim1Store]: treesize reduction 36, result has 34.5 percent of original size [2021-11-25 19:11:43,426 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 22 treesize of output 33 [2021-11-25 19:11:43,688 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-11-25 19:11:43,700 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 16 [2021-11-25 19:11:44,487 INFO L354 Elim1Store]: treesize reduction 56, result has 21.1 percent of original size [2021-11-25 19:11:44,487 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 101 treesize of output 71 [2021-11-25 19:11:44,548 INFO L354 Elim1Store]: treesize reduction 152, result has 20.4 percent of original size [2021-11-25 19:11:44,548 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 7 new quantified variables, introduced 8 case distinctions, treesize of input 197 treesize of output 165 [2021-11-25 19:11:44,559 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 83 treesize of output 66 [2021-11-25 19:11:44,577 INFO L354 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-11-25 19:11:44,577 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 6 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 38 [2021-11-25 19:11:44,599 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2021-11-25 19:11:44,664 WARN L220 Elim1Store]: Array PQE input equivalent to false [2021-11-25 19:11:44,734 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 70 treesize of output 38 [2021-11-25 19:11:44,920 INFO L354 Elim1Store]: treesize reduction 24, result has 57.9 percent of original size [2021-11-25 19:11:44,920 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 4 disjoint index pairs (out of 10 index pairs), introduced 7 new quantified variables, introduced 7 case distinctions, treesize of input 150 treesize of output 150 [2021-11-25 19:11:45,244 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2021-11-25 19:11:45,275 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 29 [2021-11-25 19:11:45,511 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 29 [2021-11-25 19:11:47,509 INFO L354 Elim1Store]: treesize reduction 24, result has 82.5 percent of original size [2021-11-25 19:11:47,509 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 1 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 9 case distinctions, treesize of input 289 treesize of output 363 [2021-11-25 19:13:20,630 INFO L354 Elim1Store]: treesize reduction 36, result has 81.3 percent of original size [2021-11-25 19:13:20,631 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 1 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 14 case distinctions, treesize of input 294 treesize of output 410 [2021-11-25 19:18:18,959 INFO L354 Elim1Store]: treesize reduction 16, result has 83.5 percent of original size [2021-11-25 19:18:18,960 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 6 select indices, 6 select index equivalence classes, 4 disjoint index pairs (out of 15 index pairs), introduced 9 new quantified variables, introduced 12 case distinctions, treesize of input 2989 treesize of output 1990