From 2a286ad5991ba06385b11e31dfdf59a31badb7b6 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 14 Jul 2017 14:33:34 +0300 Subject: [PATCH] Added goblal optimisation passes based on data flow analyses using SSA form: SCCP - Sparse Conditional Constant Propagation, DCE - Dead Code Elimination and removing of unused local variablesi. Squashed commit of the following: commit bf5ac05fc0f5f6ab9c7f2e4eaa83a11c84f471d3 Author: Dmitry Stogov Date: Fri Jul 14 14:26:40 2017 +0300 Added news entry commit 4cfa6984b1f3cd8008a0c0dc82ee3de2da02bf7c Merge: 1cdaaac 1f261d7 Author: Dmitry Stogov Date: Fri Jul 14 13:30:50 2017 +0300 Merge branch 'sccp' into dce * sccp: Bump OCI8 version for recent patch WS Fix test title Ensure that the stream position is kept between reads Turn off EXIF_DEBUG so Travis don't complain at me Don't add a new line to undefined tags in EXIF_DEBUG mode Fix compile error with EXIF_DEBUG update NEWS disable --with-pcre-valgrind on travis fix default args for --with-pcre-valgrind Enable valgrind support for PCRE by default in debug builds add oniguruma.patch to ease future upgrades SIZEOF_SIZE_T doesn't exist on AIX and POWER8 (ppc64le), keep using SIZEOF_LONG commit 1f261d77cb1cb966335097f364ace9349269c704 Merge: a32a3fb b280ba8 Author: Dmitry Stogov Date: Fri Jul 14 13:30:39 2017 +0300 Merge branch 'master' into sccp * master: Bump OCI8 version for recent patch WS Fix test title Ensure that the stream position is kept between reads Turn off EXIF_DEBUG so Travis don't complain at me Don't add a new line to undefined tags in EXIF_DEBUG mode Fix compile error with EXIF_DEBUG update NEWS disable --with-pcre-valgrind on travis fix default args for --with-pcre-valgrind Enable valgrind support for PCRE by default in debug builds add oniguruma.patch to ease future upgrades SIZEOF_SIZE_T doesn't exist on AIX and POWER8 (ppc64le), keep using SIZEOF_LONG commit 1cdaaac601cff37fa729f3e6b31dc584782a1649 Author: Dmitry Stogov Date: Fri Jul 14 13:27:12 2017 +0300 Use generic evalution mechanism for constant functions commit 75bd92a60928818358686410deec24a48e05d6da Author: Dmitry Stogov Date: Fri Jul 14 12:39:05 2017 +0300 Fixed use-def chain unlinking for "$a = 1; $a += $a;" commit 7d7746814dc382e468f9016d90c069b88b8b0f0d Author: Dmitry Stogov Date: Fri Jul 14 12:38:29 2017 +0300 Enable duplicate predecessors verification commit 6b1667f2062d7c1b55e389b03b155cbe132f5dbf Author: Dmitry Stogov Date: Fri Jul 14 11:55:20 2017 +0300 Removed duplicate definitions commit 1415b53014bf5aa1521b779debea6847db8c7940 Author: Dmitry Stogov Date: Fri Jul 14 11:51:29 2017 +0300 Enable evaluation of constant functions with 3 arguments commit ab367deef99f39dee15c6bbac45cb25eb9d29e00 Author: Dmitry Stogov Date: Fri Jul 14 11:45:13 2017 +0300 Removed deprecated check commit c51659ea8c62e4e8fbf32a0567d4f541807d6b6d Author: Dmitry Stogov Date: Fri Jul 14 11:40:42 2017 +0300 Reduce limit commit b1be5a04d783eb160a71fe26e030386b3e2771ba Author: Dmitry Stogov Date: Fri Jul 14 11:38:23 2017 +0300 Disable constant array_flip() evaluation commit 7a5b0596a149a2efc5893ea83be78ef9129009cb Author: Dmitry Stogov Date: Fri Jul 14 11:33:20 2017 +0300 Fixed comments commit 377e48b3426f9ccbcd6207acbbed87b9fdbf549d Author: Dmitry Stogov Date: Fri Jul 14 11:28:50 2017 +0300 Cast of string to long/double can not produce exception commit 228dd01af3bf6daefbd7d5be82938dec8b55b6a0 Author: Dmitry Stogov Date: Fri Jul 14 11:24:50 2017 +0300 Added missed return commit 0972a2163643757e7e270b8e1c466800aedf1308 Author: Dmitry Stogov Date: Fri Jul 14 11:22:36 2017 +0300 objects may be nested in array operands commit bd346bfa5c4c58896fabd9ab2e4d9bb85b3c1402 Author: Dmitry Stogov Date: Fri Jul 14 11:19:20 2017 +0300 ~$resource is unsupported. commit c77e45610c22e29b5f4ad7234e38a1f4e2498937 Author: Dmitry Stogov Date: Fri Jul 14 11:15:39 2017 +0300 ws commit 0b64d71109fddfec736c91546b6df978adb1f4fd Author: Dmitry Stogov Date: Fri Jul 14 11:14:40 2017 +0300 Call to zend_ssa_unlink_use_chain() shouldn't be dropped commit cb7059fcf6e51616c08d5b8a933401a94ae0b6e0 Author: Dmitry Stogov Date: Fri Jul 14 11:11:58 2017 +0300 Safer check for function name. The previous check is incorrect in ZTS build. commit 7280aba1e125fc314284d7ef1252e14d04c415a4 Author: Dmitry Stogov Date: Fri Jul 14 11:02:10 2017 +0300 Missing warning commit 54bc7b576cee33037b7e575c013e3ede726647a2 Author: Dmitry Stogov Date: Fri Jul 14 10:56:42 2017 +0300 Proper check for successors count commit ea8c004a155453b4e15684e2bd1bdb1dc99e8833 Merge: 624f76d a32a3fb Author: Dmitry Stogov Date: Thu Jul 13 15:56:26 2017 +0300 Merge branch 'sccp' into dce * sccp: fix fold Fixed bug #74866 extension_dir = "./ext" now use current directory for base add next vc15 toolset to the list Revert "Enable whole program optimization for builds without PGO, too" extend comment cleanup discontinued target commit a32a3fb67cd03b9cdab8cd15f133ef55e717408d Merge: 2722dbf 5fb2abd Author: Dmitry Stogov Date: Thu Jul 13 15:56:14 2017 +0300 Merge branch 'master' into sccp * master: fix fold Fixed bug #74866 extension_dir = "./ext" now use current directory for base add next vc15 toolset to the list Revert "Enable whole program optimization for builds without PGO, too" extend comment cleanup discontinued target commit 624f76df48db42f616bdfd02e9b26515a97c68e2 Author: Dmitry Stogov Date: Thu Jul 13 12:30:27 2017 +0300 Set RETURN_VALUE_UNUSED instead of additional FREE opcode, if possible. Keep alive dead instructions that have to free two temporary variables. commit 94c9b26695702e863ebeb40fa3cce5f5f2db7744 Author: Dmitry Stogov Date: Thu Jul 13 11:51:14 2017 +0300 More accurate "vararg" handling in DCE commit 665ed8491ca07cd6d3363abf42c5777e132a3da1 Author: Dmitry Stogov Date: Thu Jul 13 09:31:45 2017 +0300 Improved DCE performance, by avoiding redundand checks and repeatable iterations. commit 3f42ce18ba4420aabb9b07b838096cce340d06b7 Author: Dmitry Stogov Date: Wed Jul 12 23:03:11 2017 +0300 Added few more instructions without side effects and exceptions commit b17178f991c095d9137c1536b53b933208e575bf Author: Dmitry Stogov Date: Wed Jul 12 20:39:02 2017 +0300 Temprary enable SSA validation in DEBUG build commit e238a8dc79debcf2f833e07323f975173aec6205 Author: Dmitry Stogov Date: Wed Jul 12 20:37:53 2017 +0300 Inegrate SSA validation developed by Nikita commit a247cee80b47ca335162e8bd46d06274f8af5a4d Author: Dmitry Stogov Date: Wed Jul 12 20:31:27 2017 +0300 Perform DCE pass before other DFA optimisations, to properly reconstruct "no value" use-def chains. commit a651564f299e3b413af1146149de0d7eec0dfb28 Merge: 06f6eb0 2722dbf Author: Dmitry Stogov Date: Wed Jul 12 18:55:05 2017 +0300 Merge branch 'sccp' into dce * sccp: Resources should be closed during object destructioin, not during freeing. Guard against AppVeyor losing deps issue increase poll timeout as false positives mitigation Value of EG(user_exception_handler) should't relive request boundary sodium ext: remove function names before exception messages sodium ext: update the crypto_kx_*() API to the libsodium one Revert "fix macro redifinitions" commit 2722dbfdf54702c8b429ed792e96f91219031eb6 Merge: 6595ea3 09d3b73 Author: Dmitry Stogov Date: Wed Jul 12 18:54:48 2017 +0300 Merge branch 'master' into sccp * master: Resources should be closed during object destructioin, not during freeing. Guard against AppVeyor losing deps issue increase poll timeout as false positives mitigation Value of EG(user_exception_handler) should't relive request boundary sodium ext: remove function names before exception messages sodium ext: update the crypto_kx_*() API to the libsodium one Revert "fix macro redifinitions" commit 06f6eb0e6877d8b26c621f5627587539ebcc781f Author: Dmitry Stogov Date: Wed Jul 12 14:52:28 2017 +0300 Use zend_ssa_is_no_val_use() instead of zend_has_improper_op1_use() commit 4b64dbb30d519be359c44ad4f3802e93a7f5fa65 Author: Dmitry Stogov Date: Wed Jul 12 13:07:14 2017 +0300 Check if instruction may throw exception only for instructions without known side effects. Always disable removing ASSIGN and UNSET_VAR that may throw. commit c5aa1f47cd16290c77fb988504dc0dd8bad242a3 Author: Dmitry Stogov Date: Wed Jul 12 11:21:07 2017 +0300 Use existing bit commit c2af153baea6e05401f78a856a8ae436e5f37bf9 Author: Dmitry Stogov Date: Wed Jul 12 11:10:48 2017 +0300 Updated Windows build commit de5e8fc12971e55c81b0768daa96adcd6074038e Merge: 8c0de53 6595ea3 Author: Dmitry Stogov Date: Wed Jul 12 11:10:12 2017 +0300 Merge branch 'sccp' into dce * sccp: (29 commits) Use existing bit Updated Windows build Fixed compilation error Remove debug code We need to check for the length here too, or we crash and no one likes that! :( * Implemented #65187 (exif_read_data/thumbnail: add support for stream resource) * ext/exif now uses FAST_ZPP Remove extraneous configure flag Revert "remove excessive checks and fix warnings" parametrize zip names Upgrade bundled PCRE to 8.41 Updated NEWS file with LDAP changes Fixed removing all controls by passing an empty array to ldap_set_option Filled in NEWS file with ext/ldap last modifications change order, allow to build as shared extension restore file deleted by mistake in a merge commit Fix segfault in php_stream_context_get_option call remove excessive checks and fix warnings fix macro redifinitions fix symbol availability and ws Remove this for now, as not found ... commit 6595ea3420b686d1bfe49fbd5893b6a42115c60b Author: Dmitry Stogov Date: Wed Jul 12 10:27:02 2017 +0300 Use existing bit commit f0bfd36cb822dbbe28df827a53a2ed96aa61051f Author: Dmitry Stogov Date: Wed Jul 12 10:21:22 2017 +0300 Updated Windows build commit a9bd7c89f28cf99933a4d3d026a6da5f5e3ca0f7 Merge: d1eb5ed 2b7d3fb Author: Dmitry Stogov Date: Wed Jul 12 09:51:32 2017 +0300 Merge branch 'master' into sccp * master: (27 commits) Fixed compilation error Remove debug code We need to check for the length here too, or we crash and no one likes that! :( * Implemented #65187 (exif_read_data/thumbnail: add support for stream resource) * ext/exif now uses FAST_ZPP Remove extraneous configure flag Revert "remove excessive checks and fix warnings" parametrize zip names Upgrade bundled PCRE to 8.41 Updated NEWS file with LDAP changes Fixed removing all controls by passing an empty array to ldap_set_option Filled in NEWS file with ext/ldap last modifications change order, allow to build as shared extension restore file deleted by mistake in a merge commit Fix segfault in php_stream_context_get_option call remove excessive checks and fix warnings fix macro redifinitions fix symbol availability and ws Remove this for now, as not found fix authors NEWS for Sodium ... commit 8c0de53e5f599c83fa03c78931527ab4ff14cf93 Author: Dmitry Stogov Date: Tue Jul 11 21:54:36 2017 +0300 Initial integration of Dead Code Elimination (DCE) and unused variable removing passes, originally developed in https://github.com/nikic/php-src/tree/opt, into DFA optimization pass. commit d1eb5ede3a2b9a0bf57e06783f7913a6383f5d6d Author: Dmitry Stogov Date: Tue Jul 11 12:19:11 2017 +0300 Proper SSA reconstruction for "$a = $a;" commit 4872d139b55c22c2325459dba0ee557c708567b5 Author: Dmitry Stogov Date: Tue Jul 11 11:57:33 2017 +0300 Replace conditions, that should be always true, by ZEND_ASSERT() commit 9915b1f5cd2bdd92d0cc5e90244a90fbef06740b Author: Dmitry Stogov Date: Tue Jul 11 11:56:51 2017 +0300 Fixed pass name commit d26ff1b88d3b3b1e8742f2e7812ae5e2531958a6 Author: Dmitry Stogov Date: Tue Jul 11 11:55:47 2017 +0300 Don't create identical predecessors commit 0625fbe32bd66b7bcca29e65b131f0cfccd3e074 Author: Dmitry Stogov Date: Tue Jul 11 09:36:07 2017 +0300 Update unreachable blocks. commit 9d7d409e6abda5c2e13458f01b8133095fb68531 Author: Dmitry Stogov Date: Tue Jul 11 09:28:49 2017 +0300 Keep consistent cfg.map[] commit 85a86e58b220eaf2012f652b97fbeb2d2f85646d Author: Dmitry Stogov Date: Tue Jul 11 02:36:14 2017 +0300 Remove unusded phi commit d5e0f2df4c76656bbe5973e69e12e1b7415de5ee Author: Dmitry Stogov Date: Tue Jul 11 02:35:00 2017 +0300 Don't clear phi->spources[] too early. commit a90ed34295a0bab09c00bb7001a368a858a38399 Author: Dmitry Stogov Date: Mon Jul 10 21:29:39 2017 +0300 Make SCCP to remove dead live ranges. commit 320237f3d84b872dfa096b9a604ae4d5b4d28c8e Merge: 63bbed5 7be2637 Author: Dmitry Stogov Date: Mon Jul 10 17:35:21 2017 +0300 Merge branch 'master' into sccp * master: Fixed memory leak introduced by 7cb5bdf64a95bd70623d33d6ea122c13b01113bd eliminate casts remove checks for eol dependencies improve test Small fix in ext/ldap, Moved vars definitions to the beginning of the block using them ZipArchive implements countable, added ZipArchive::count() method commit 63bbed5e71432d14217b591de511f09937a3c00c Author: Dmitry Stogov Date: Mon Jul 10 17:01:15 2017 +0300 Evaluation of few more constant functions commit 07f45d8a3dbfa67bc28c9ef4bb14c753816f4e44 Author: Dmitry Stogov Date: Mon Jul 10 16:22:47 2017 +0300 Properly unlinking dead blocks from predecessors/successors and dominators commit 502002aa6e11452ed27829f7e29604b27fc69ad2 Author: Dmitry Stogov Date: Mon Jul 10 13:33:14 2017 +0300 Replacel constant JMPZ/NZ/ZNZ by JMP or NOP commit 3253e61b66b3aa324115ec57ff1cb271ca27dc14 Merge: e7f69f0 161c378 Author: Dmitry Stogov Date: Mon Jul 10 12:22:39 2017 +0300 Merge branch 'master' into sccp * master: Revert "Fixed bug #74878" Upgrading note for #74837 Fixed bug #74837 - NEWS Implement Countable for DomNodeList and DOMNamedNodeMap (Request #74837) Fix #49649 - Handle property visibility changes on unserialization commit e7f69f07fc649692218d01dab34b8f8555a6f88c Author: Dmitry Stogov Date: Mon Jul 10 12:15:08 2017 +0300 Prevent compile-time evaluation of implode() with arguments causing run-time warnings commit 0e882f189a01b6ee648420776fb473c1efd22380 Author: Dmitry Stogov Date: Mon Jul 10 11:54:04 2017 +0300 Constant evaluation of ini_get() for some safe cases commit 9e36a748b28850bd15ac621879e1d28ed8e36169 Author: Dmitry Stogov Date: Mon Jul 10 11:13:37 2017 +0300 Constant evaluation of implode() commit e73046e266617ae23caa7f40344fc6e8e41e3c56 Author: Dmitry Stogov Date: Mon Jul 10 10:51:23 2017 +0300 Fixed uninitialized value commit f5e2e8e68cc46cfc1380d000672d01b243ad7f59 Author: Dmitry Stogov Date: Mon Jul 10 10:05:37 2017 +0300 Remove (compact) unused constants after SCCP pass commit f0b7bb86ebe93373a02ef36029f76239ba9ec1d4 Merge: e69d4f6 cfacf84 Author: Dmitry Stogov Date: Mon Jul 10 09:10:00 2017 +0300 Merge branch 'master' into sccp * master: (37 commits) #73594 tests only check the extra params if dns_get_record is successful Fixed bug #74852 (property_exists returns true on unknown DateInterval property) fix uninitialized var fix comparison warning comply with POSIX signature fix warning remove some casts cleanup casts remove useless cast eliminate casts sync vim mode lines in main [ci skip] update NEWS [ci skip] update NEWS [ci skip] update NEWS Fixed bug #74883 SQLite3::__construct() produces "out of memory" exception with invalid flags Silent compiler warning Fix test Deprecated the read_exif_data() alias Add myself as exif maintainer update libs versions ... commit e69d4f61409c473ae36d85c3779ad5f786fecdc0 Author: Dmitry Stogov Date: Fri Jul 7 12:51:41 2017 +0300 Avoid in-place modification of referenced data commit 58f7c17978dec7b5fe6fe80b4efc55e2168bab61 Author: Dmitry Stogov Date: Fri Jul 7 12:33:24 2017 +0300 Use arena for temporary data. commit 93d3e7ddc22f1bc7323abae2256b0b50bc1f8b29 Author: Dmitry Stogov Date: Fri Jul 7 11:54:47 2017 +0300 Made sccp_ctx to be an "extension" of scdf_ctx and remove duplicate data. commit f810c6f7c47b03412c61878b761e1bb687fbcf28 Author: Dmitry Stogov Date: Fri Jul 7 11:20:48 2017 +0300 Improved SSCP integration commit d17ed887f304af0f6ccba76a3dbfca888867ea01 Merge: d90805a 29653da Author: Dmitry Stogov Date: Fri Jul 7 10:22:37 2017 +0300 Merge branch 'master' into sccp * master: Fixed bug #74873 (Minor BC break: PCRE_JIT changes output of preg_match()). Fixed bug #72324 (imap_mailboxmsginfo() return wrong size) Fix redefine warnings Expand sb's name and capitalize my own Write the URL on a new line, so that it is easier copyable commit d90805a40bd5d75d197f7b95c69680f636932868 Merge: 2e5e03b fc336c7 Author: Dmitry Stogov Date: Thu Jul 6 23:07:04 2017 +0300 Merge branch 'master' into sccp * master: Added missed dump of "main" script code replace the stack var by a macro [ci skip] sync NEWS minor fix for web announce add missing NEWS entry for #74087 and also fix the formatting move NEWS entry to the correct place, also bump the version commit 2e5e03b673cb86ee0fa6be06496553fa6b8c52e7 Author: Dmitry Stogov Date: Thu Jul 6 23:03:41 2017 +0300 Call info should be removed, but at least we should prevent incorrect stack adjustment. commit 1ee9110b35eab79f74d08278c104c92796740fa7 Author: Dmitry Stogov Date: Thu Jul 6 19:34:43 2017 +0300 Remove NOP instructions, introduced bvy SCCP. This commit discloses unrelated issue caused ext/soap/tests/bug70211.phpt failure. commit 9a2f50070d1afde8ee4784a1dade2537e1ac30d5 Author: Dmitry Stogov Date: Thu Jul 6 16:34:02 2017 +0300 Avoid useless iterations for first SSA variablesi, always marked BOT. commit c57dd7c6efb98c89a8c87af0eaad76b71c9cda16 Author: Dmitry Stogov Date: Thu Jul 6 16:33:46 2017 +0300 Use reference-counting commit 90f822d68ef1cb68befa3fff289c9e8d1b2068c8 Author: Dmitry Stogov Date: Thu Jul 6 14:00:22 2017 +0300 Support for few more opcodes commit cffee2f7e5bb4198e645e291fafe5690443cf26c Author: Dmitry Stogov Date: Thu Jul 6 12:35:13 2017 +0300 Combined constants substitutaion and dead instruction removing in single pass. This eleminates substitution in dead instructions. commit f890375c16052a9d79bf77c9021914cb9c6616f8 Author: Dmitry Stogov Date: Thu Jul 6 10:34:48 2017 +0300 Use reference-counting instead of duplication commit db0cd64dfa7a2ff809b49a049074b5fa39d37314 Author: Dmitry Stogov Date: Thu Jul 6 03:04:27 2017 +0300 Improved SCDF<->SCCP interface - "get_feasible_successors" callback is changed into "mark_feasible_successors" and should mark necessary edges through scdf_mark_edge_feasible() - SCDF takes care about OP_DATA instruction - SCDF code is re-arranged to avoid repeatable checks commit e0ad5dd48942c71033fad985c591549a35c21ef3 Author: Dmitry Stogov Date: Thu Jul 6 00:55:40 2017 +0300 Changed representation of "feasible_edges", using one bit per edge. commit afee3138fe49588b3967f54bf66375f880a51924 Author: Dmitry Stogov Date: Thu Jul 6 00:49:56 2017 +0300 Revert "Don't propagate unused values" This reverts commit 84e5bfd4304d34e3a7107db71783882013f8de59. commit 84e5bfd4304d34e3a7107db71783882013f8de59 Author: Dmitry Stogov Date: Wed Jul 5 23:39:42 2017 +0300 Don't propagate unused values commit d4f15b95061a8a2303d90e6e54effeb9733f90b7 Author: Dmitry Stogov Date: Wed Jul 5 23:39:10 2017 +0300 Don't visit the same Phi twice commit 2558311b4d530fb84539db304d03dfeba5eda789 Merge: 722a59d 7bb4ae5 Author: Dmitry Stogov Date: Wed Jul 5 21:51:06 2017 +0300 Merge branch 'master' into sccp * master: Fixed final dump "after optimizer" commit 722a59ddb12e641aea99ca8853ef921c4fdf9819 Author: Dmitry Stogov Date: Wed Jul 5 21:09:29 2017 +0300 SCCP doesn't support VERIFY_RETURN_TYPE (ext/opcache/tests/bug73789.phpt failure) commit 7084fade4dcb74415f0644d8e207f0fab6c6509d Author: Dmitry Stogov Date: Wed Jul 5 20:37:21 2017 +0300 Fixed SSA reconstruction commit 37ec4e0845a5b25fe2b523452d32dba22605d2e3 Author: Dmitry Stogov Date: Wed Jul 5 19:34:46 2017 +0300 Disable constant propagation for variables that can be modified indirectly commit 4bb9b6526e44c2f324f9a7c08890ab9bdedd639c Merge: 6800460 73d5097 Author: Dmitry Stogov Date: Wed Jul 5 19:17:04 2017 +0300 Merge branch 'master' into sccp * master: (43 commits) Keep information about SSA variables, that may be modified indirectly. Added constants for known ldap controls OID and tests for ldap_get/set_option for controls Added support for controls to ldap_get_option [ci skip] sync NEWS NEWS for oniguruma Patch from the upstream git https://github.com/kkos/oniguruma/issues/60 (CVE-2017-9228) Patch from the upstream git https://github.com/kkos/oniguruma/issues/59 (CVE-2017-9229) b690371bbf97794b4a1d3f295d4fb9a8b05d402d Modified for onig 5.9.6 Patch from the upstream git https://github.com/kkos/oniguruma/issues/58 (CVE-2017-9227) Patch from the upstream git https://github.com/kkos/oniguruma/issues/57 (CVE-2017-9224) Patch from the upstream git https://github.com/kkos/oniguruma/issues/55 (CVE-2017-9226) b4bf968ad52afe14e60a2dc8a95d3555c543353a Modified for onig 5.9.6 f015fbdd95f76438cd86366467bb2b39870dd7c6 Modified for onig 5.9.6 valid_symbol_table removed Improve fix for #74145 Fix wddx Fix tests Fixed bug #74111 Fix bug #74603 - use correct buffer size Fix bug #74651 - check EVP_SealInit as it can return -1 Update NEWS Fix bug #74087 Fixed parsing of strange formats with mixed month/day and time strings ... commit 680046086c17b938e0288fca820668a183b86834 Author: Dmitry Stogov Date: Wed Jul 5 16:14:38 2017 +0300 Support for few more internal functions evaluation commit 74a29468ef14260ea3c210a2d1e3548806c81339 Author: Dmitry Stogov Date: Wed Jul 5 13:42:55 2017 +0300 Disabled evaluation of strpos() with empty needle. commit e8908946e52127727da9f0dd22a053befe8bf848 Author: Dmitry Stogov Date: Wed Jul 5 13:17:30 2017 +0300 Replace calls to in_array() with constant array by IN_ARRAY instruction after SCCP. commit 4e8fa2c3dd087a49ba90a3ef8231cc81f0399548 Author: Dmitry Stogov Date: Wed Jul 5 00:58:12 2017 +0300 Initial integration of Sparse Conditional Constant Propagation (SCCP), originally developed in https://github.com/nikic/php-src/tree/opt, into DFA optimization pass. --- NEWS | 5 + Zend/zend_bitset.h | 8 + ext/opcache/Optimizer/compact_vars.c | 112 ++ ext/opcache/Optimizer/dce.c | 647 ++++++++ ext/opcache/Optimizer/dfa_pass.c | 214 ++- ext/opcache/Optimizer/sccp.c | 1445 +++++++++++++++++ ext/opcache/Optimizer/scdf.c | 228 +++ ext/opcache/Optimizer/scdf.h | 99 ++ ext/opcache/Optimizer/ssa_integrity.c | 369 +++++ ext/opcache/Optimizer/zend_cfg.c | 16 +- ext/opcache/Optimizer/zend_cfg.h | 1 + ext/opcache/Optimizer/zend_inference.c | 325 +++- ext/opcache/Optimizer/zend_inference.h | 5 + ext/opcache/Optimizer/zend_optimizer.c | 121 +- ext/opcache/Optimizer/zend_optimizer.h | 6 +- .../Optimizer/zend_optimizer_internal.h | 8 +- ext/opcache/Optimizer/zend_ssa.c | 454 +++++- ext/opcache/Optimizer/zend_ssa.h | 124 ++ ext/opcache/config.m4 | 4 + ext/opcache/config.w32 | 2 +- ext/opcache/tests/ssa_bug_007.phpt | 23 + 21 files changed, 4153 insertions(+), 63 deletions(-) create mode 100644 ext/opcache/Optimizer/compact_vars.c create mode 100644 ext/opcache/Optimizer/dce.c create mode 100644 ext/opcache/Optimizer/sccp.c create mode 100644 ext/opcache/Optimizer/scdf.c create mode 100644 ext/opcache/Optimizer/scdf.h create mode 100644 ext/opcache/Optimizer/ssa_integrity.c create mode 100644 ext/opcache/tests/ssa_bug_007.phpt diff --git a/NEWS b/NEWS index 598edb21f6..220a73f77c 100644 --- a/NEWS +++ b/NEWS @@ -44,6 +44,11 @@ PHP NEWS - LDAP: . Fixed passing an empty array to ldap_set_option for client or server controls. +- Opcache: + . Added goblal optimisation passes based on data flow analyses using SSA form: + SCCP - Sparse Conditional Constant Propagation, DCE - Dead Code Elimination + and removing of unused local variables (Nikita, Dmitry) + - OpenSSL: . Fixed bug #74651 (negative-size-param (-1) in memcpy in zif_openssl_seal()). (Stas) diff --git a/Zend/zend_bitset.h b/Zend/zend_bitset.h index da2dcacd92..98a46f9640 100644 --- a/Zend/zend_bitset.h +++ b/Zend/zend_bitset.h @@ -245,6 +245,14 @@ static inline int zend_bitset_last(zend_bitset set, uint32_t len) } \ } while (0) +static inline int zend_bitset_pop_first(zend_bitset set, uint32_t len) { + int i = zend_bitset_first(set, len); + if (i >= 0) { + zend_bitset_excl(set, i); + } + return i; +} + #endif /* _ZEND_BITSET_H_ */ /* diff --git a/ext/opcache/Optimizer/compact_vars.c b/ext/opcache/Optimizer/compact_vars.c new file mode 100644 index 0000000000..c5a9b79553 --- /dev/null +++ b/ext/opcache/Optimizer/compact_vars.c @@ -0,0 +1,112 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, Removing unused variables | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Nikita Popov | + +----------------------------------------------------------------------+ +*/ + +#include "ZendAccelerator.h" +#include "Optimizer/zend_optimizer_internal.h" +#include "zend_bitset.h" + +/* This pass removes all CVs that are completely unused. It does *not* merge any CVs. + * This pass does not operate on SSA form anymore. */ +void zend_optimizer_compact_vars(zend_op_array *op_array) { + int i; + + ALLOCA_FLAG(use_heap1); + ALLOCA_FLAG(use_heap2); + uint32_t used_cvs_len = zend_bitset_len(op_array->last_var); + zend_bitset used_cvs = ZEND_BITSET_ALLOCA(used_cvs_len, use_heap1); + uint32_t *cv_map = do_alloca(op_array->last_var * sizeof(uint32_t), use_heap2); + uint32_t num_cvs, tmp_offset; + + /* Determine which CVs are used */ + zend_bitset_clear(used_cvs, used_cvs_len); + for (i = 0; i < op_array->last; i++) { + zend_op *opline = &op_array->opcodes[i]; + if (opline->op1_type == IS_CV) { + zend_bitset_incl(used_cvs, VAR_NUM(opline->op1.var)); + } + if (opline->op2_type == IS_CV) { + zend_bitset_incl(used_cvs, VAR_NUM(opline->op2.var)); + } + if (opline->result_type == IS_CV) { + zend_bitset_incl(used_cvs, VAR_NUM(opline->result.var)); + } + } + + num_cvs = 0; + for (i = 0; i < op_array->last_var; i++) { + if (zend_bitset_in(used_cvs, i)) { + cv_map[i] = num_cvs++; + } else { + cv_map[i] = (uint32_t) -1; + } + } + + free_alloca(used_cvs, use_heap1); + if (num_cvs == op_array->last_var) { + free_alloca(cv_map, use_heap2); + return; + } + + ZEND_ASSERT(num_cvs < op_array->last_var); + tmp_offset = op_array->last_var - num_cvs; + + /* Update CV and TMP references in opcodes */ + for (i = 0; i < op_array->last; i++) { + zend_op *opline = &op_array->opcodes[i]; + if (opline->op1_type == IS_CV) { + opline->op1.var = NUM_VAR(cv_map[VAR_NUM(opline->op1.var)]); + } else if (opline->op1_type & (IS_VAR|IS_TMP_VAR)) { + opline->op1.var -= sizeof(zval) * tmp_offset; + } + if (opline->op2_type == IS_CV) { + opline->op2.var = NUM_VAR(cv_map[VAR_NUM(opline->op2.var)]); + } else if (opline->op2_type & (IS_VAR|IS_TMP_VAR)) { + opline->op2.var -= sizeof(zval) * tmp_offset; + } + if (opline->result_type == IS_CV) { + opline->result.var = NUM_VAR(cv_map[VAR_NUM(opline->result.var)]); + } else if (opline->result_type & (IS_VAR|IS_TMP_VAR)) { + opline->result.var -= sizeof(zval) * tmp_offset; + } + } + + /* Update TMP references in live ranges */ + if (op_array->live_range) { + for (i = 0; i < op_array->last_live_range; i++) { + op_array->live_range[i].var -= sizeof(zval) * tmp_offset; + } + } + + /* Update CV name table */ + { + zend_string **names = safe_emalloc(sizeof(zend_string *), num_cvs, 0); + for (i = 0; i < op_array->last_var; i++) { + if (cv_map[i] != (uint32_t) -1) { + names[cv_map[i]] = op_array->vars[i]; + } else { + zend_string_release(op_array->vars[i]); + } + } + efree(op_array->vars); + op_array->vars = names; + } + + op_array->last_var = num_cvs; + + free_alloca(cv_map, use_heap2); +} diff --git a/ext/opcache/Optimizer/dce.c b/ext/opcache/Optimizer/dce.c new file mode 100644 index 0000000000..2c21154ef7 --- /dev/null +++ b/ext/opcache/Optimizer/dce.c @@ -0,0 +1,647 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, DCE - Dead Code Elimination | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Nikita Popov | + +----------------------------------------------------------------------+ +*/ + +#include "ZendAccelerator.h" +#include "Optimizer/zend_optimizer_internal.h" +#include "Optimizer/zend_inference.h" +#include "Optimizer/zend_ssa.h" +#include "Optimizer/zend_func_info.h" +#include "Optimizer/zend_call_graph.h" +#include "zend_bitset.h" + +/* This pass implements a form of dead code elimination (DCE). The algorithm optimistically assumes + * that all instructions and phis are dead. Instructions with immediate side-effects are then marked + * as live. We then recursively (using a worklist) propagate liveness to the instructions that def + * the used operands. + * + * Notes: + * * This pass does not perform unreachable code elimination. This happens as part of the SCCP + * pass. + * * The DCE is performed without taking control-dependence into account, i.e. all conditional + * branches are assumed to be live. It's possible to take control-dependence into account using + * the DCE algorithm described by Cytron et al., however it requires the construction of a + * postdominator tree and of postdominance frontiers, which does not seem worthwhile at this + * point. + * * We separate intrinsic side-effects from potential side-effects in the form of notices thrown + * by the instruction (in case we want to make this configurable). See may_have_side_effect() and + * zend_may_throw(). + * * We often cannot DCE assignments and unsets while guaranteeing that dtors run in the same + * order. There is an optimization option to allow reordering of dtor effects. + */ + +typedef struct { + zend_ssa *ssa; + zend_op_array *op_array; + zend_bitset instr_dead; + zend_bitset phi_dead; + zend_bitset instr_worklist; + zend_bitset phi_worklist; + zend_bitset phi_worklist_no_val; + uint32_t instr_worklist_len; + uint32_t phi_worklist_len; + unsigned reorder_dtor_effects : 1; +} context; + +static inline zend_bool is_bad_mod(const zend_ssa *ssa, int use, int def) { + if (def < 0) { + /* This modification is not tracked by SSA, assume the worst */ + return 1; + } + if (ssa->var_info[use].type & MAY_BE_REF) { + /* Modification of reference may have side-effect */ + return 1; + } + return 0; +} + +static inline zend_bool may_have_side_effects( + zend_op_array *op_array, zend_ssa *ssa, + const zend_op *opline, const zend_ssa_op *ssa_op, + zend_bool reorder_dtor_effects) { + switch (opline->opcode) { + case ZEND_NOP: + case ZEND_IS_IDENTICAL: + case ZEND_IS_NOT_IDENTICAL: + case ZEND_QM_ASSIGN: + case ZEND_FREE: + case ZEND_TYPE_CHECK: + case ZEND_DEFINED: + case ZEND_ADD: + case ZEND_SUB: + case ZEND_MUL: + case ZEND_POW: + case ZEND_BW_OR: + case ZEND_BW_AND: + case ZEND_BW_XOR: + case ZEND_CONCAT: + case ZEND_FAST_CONCAT: + case ZEND_DIV: + case ZEND_MOD: + case ZEND_BOOL_XOR: + case ZEND_BOOL: + case ZEND_BOOL_NOT: + case ZEND_BW_NOT: + case ZEND_SL: + case ZEND_SR: + case ZEND_IS_EQUAL: + case ZEND_IS_NOT_EQUAL: + case ZEND_IS_SMALLER: + case ZEND_IS_SMALLER_OR_EQUAL: + case ZEND_CASE: + case ZEND_CAST: + case ZEND_ROPE_INIT: + case ZEND_ROPE_ADD: + case ZEND_ROPE_END: + case ZEND_INIT_ARRAY: + case ZEND_ADD_ARRAY_ELEMENT: + case ZEND_SPACESHIP: + case ZEND_STRLEN: + case ZEND_COUNT: + case ZEND_GET_TYPE: + case ZEND_ISSET_ISEMPTY_THIS: + case ZEND_ISSET_ISEMPTY_DIM_OBJ: + case ZEND_FETCH_DIM_IS: + case ZEND_ISSET_ISEMPTY_VAR: + case ZEND_FETCH_IS: + /* No side effects */ + return 0; + case ZEND_JMP: + case ZEND_JMPZ: + case ZEND_JMPNZ: + case ZEND_JMPZNZ: + case ZEND_JMPZ_EX: + case ZEND_JMPNZ_EX: + case ZEND_JMP_SET: + case ZEND_COALESCE: + case ZEND_ASSERT_CHECK: + /* For our purposes a jumps and branches are side effects. */ + return 1; + case ZEND_BEGIN_SILENCE: + case ZEND_END_SILENCE: + case ZEND_ECHO: + case ZEND_INCLUDE_OR_EVAL: + case ZEND_THROW: + case ZEND_EXT_STMT: + case ZEND_EXT_FCALL_BEGIN: + case ZEND_EXT_FCALL_END: + case ZEND_EXT_NOP: + case ZEND_TICKS: + case ZEND_YIELD: + case ZEND_YIELD_FROM: + /* Intrinsic side effects */ + return 1; + case ZEND_DO_FCALL: + case ZEND_DO_FCALL_BY_NAME: + case ZEND_DO_ICALL: + case ZEND_DO_UCALL: + /* For now assume all calls have side effects */ + return 1; + case ZEND_RECV: + case ZEND_RECV_INIT: + /* Even though RECV_INIT can be side-effect free, these cannot be simply dropped + * due to the prologue skipping code. */ + return 1; + case ZEND_ASSIGN_REF: + return 1; + case ZEND_ASSIGN: + { + if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)) { + return 1; + } + if (!reorder_dtor_effects) { + if (opline->op2_type != IS_CONST && (OP2_INFO() & MAY_HAVE_DTOR)) { + /* DCE might shorten lifetime */ + return 1; + } + } + return 0; + } + case ZEND_UNSET_VAR: + { + uint32_t t1 = OP1_INFO(); + if (!(opline->extended_value & ZEND_QUICK_SET)) { + return 1; + } + if (t1 & MAY_BE_REF) { + /* We don't consider uses as the LHS of an assignment as real uses during DCE, so + * an unset may be considered dead even if there is a later assignment to the + * variable. Removing the unset in this case would not be correct if the variable + * is a reference, because unset breaks references. */ + return 1; + } + return 0; + } + case ZEND_PRE_INC: + case ZEND_POST_INC: + case ZEND_PRE_DEC: + case ZEND_POST_DEC: + return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def); + case ZEND_ASSIGN_ADD: + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + case ZEND_ASSIGN_CONCAT: + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + case ZEND_ASSIGN_POW: + if (opline->extended_value) { + /* ASSIGN_DIM has no side-effect, but we can't deal with OP_DATA anyway */ + return 1; + } + return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def); + default: + /* For everything we didn't handle, assume a side-effect */ + return 1; + } +} + +static zend_always_inline void add_to_worklists(context *ctx, int var_num, int check) { + zend_ssa_var *var = &ctx->ssa->vars[var_num]; + if (var->definition >= 0) { + if (!check || zend_bitset_in(ctx->instr_dead, var->definition)) { + zend_bitset_incl(ctx->instr_worklist, var->definition); + } + } else if (var->definition_phi) { + if (!check || zend_bitset_in(ctx->phi_dead, var_num)) { + zend_bitset_incl(ctx->phi_worklist, var_num); + } + } +} + +static inline void add_to_phi_worklist_no_val(context *ctx, int var_num) { + zend_ssa_var *var = &ctx->ssa->vars[var_num]; + if (var->definition_phi && zend_bitset_in(ctx->phi_dead, var_num)) { + zend_bitset_incl(ctx->phi_worklist_no_val, var_num); + } +} + +static zend_always_inline void add_operands_to_worklists(context *ctx, zend_op *opline, zend_ssa_op *ssa_op, int check) { + if (ssa_op->result_use >= 0) { + add_to_worklists(ctx, ssa_op->result_use, check); + } + if (ssa_op->op1_use >= 0) { + if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op1_use)) { + add_to_worklists(ctx, ssa_op->op1_use, check); + } else { + add_to_phi_worklist_no_val(ctx, ssa_op->op1_use); + } + } + if (ssa_op->op2_use >= 0) { + if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op2_use)) { + add_to_worklists(ctx, ssa_op->op2_use, check); + } else { + add_to_phi_worklist_no_val(ctx, ssa_op->op2_use); + } + } +} + +static zend_always_inline void add_phi_sources_to_worklists(context *ctx, zend_ssa_phi *phi, int check) { + zend_ssa *ssa = ctx->ssa; + int source; + FOREACH_PHI_SOURCE(phi, source) { + add_to_worklists(ctx, source, check); + } FOREACH_PHI_SOURCE_END(); +} + +static inline zend_bool is_var_dead(context *ctx, int var_num) { + zend_ssa_var *var = &ctx->ssa->vars[var_num]; + if (var->definition_phi) { + return zend_bitset_in(ctx->phi_dead, var_num); + } else if (var->definition >= 0) { + return zend_bitset_in(ctx->instr_dead, var->definition); + } else { + /* Variable has no definition, so either the definition has already been removed (var is + * dead) or this is one of the implicit variables at the start of the function (for our + * purposes live) */ + return var_num >= ctx->op_array->last_var; + } +} + +// Sometimes we can mark the var as EXT_UNUSED +static zend_bool try_remove_var_def(context *ctx, int free_var, int use_chain, zend_op *opline) { + if (use_chain >= 0) { + return 0; + } + zend_ssa_var *var = &ctx->ssa->vars[free_var]; + int def = var->definition; + + if (def >= 0) { + zend_ssa_op *def_op = &ctx->ssa->ops[def]; + + if (def_op->result_def == free_var + && var->phi_use_chain == NULL + && var->use_chain == (opline - ctx->op_array->opcodes)) { + zend_op *def_opline = &ctx->op_array->opcodes[def]; + + switch (def_opline->opcode) { + case ZEND_ASSIGN: + case ZEND_ASSIGN_REF: + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + case ZEND_ASSIGN_ADD: + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + case ZEND_ASSIGN_CONCAT: + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + case ZEND_ASSIGN_POW: + case ZEND_PRE_INC: + case ZEND_POST_INC: + case ZEND_PRE_DEC: + case ZEND_POST_DEC: + case ZEND_PRE_INC_OBJ: + case ZEND_POST_INC_OBJ: + case ZEND_PRE_DEC_OBJ: + case ZEND_POST_DEC_OBJ: + case ZEND_DO_ICALL: + case ZEND_DO_UCALL: + case ZEND_DO_FCALL_BY_NAME: + case ZEND_DO_FCALL: + case ZEND_INCLUDE_OR_EVAL: + case ZEND_YIELD: + case ZEND_YIELD_FROM: + case ZEND_ASSERT_CHECK: + def_opline->result_type = IS_UNUSED; + def_opline->result.var = 0; + def_op->result_def = -1; + var->definition = -1; + return 1; + default: + break; + } + } + } + return 0; +} + +/* Returns whether the instruction has been DCEd */ +static zend_bool dce_instr(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) { + zend_ssa *ssa = ctx->ssa; + int free_var = -1; + zend_uchar free_var_type; + + if (opline->opcode == ZEND_NOP) { + return 0; + } + + /* We mark FREEs as dead, but they're only really dead if the destroyed var is dead */ + if (opline->opcode == ZEND_FREE && !is_var_dead(ctx, ssa_op->op1_use)) { + return 0; + } + + if ((opline->op1_type & (IS_VAR|IS_TMP_VAR)) && !is_var_dead(ctx, ssa_op->op1_use)) { + if (!try_remove_var_def(ctx, ssa_op->op1_use, ssa_op->op1_use_chain, opline)) { + free_var = ssa_op->op1_use; + free_var_type = opline->op1_type; + } + } + if ((opline->op2_type & (IS_VAR|IS_TMP_VAR)) && !is_var_dead(ctx, ssa_op->op2_use)) { + if (!try_remove_var_def(ctx, ssa_op->op2_use, ssa_op->op2_use_chain, opline)) { + if (free_var >= 0) { + // TODO: We can't free two vars. Keep instruction alive. + zend_bitset_excl(ctx->instr_dead, opline - ctx->op_array->opcodes); + return 0; + } + free_var = ssa_op->op2_use; + free_var_type = opline->op2_type; + } + } + + zend_ssa_rename_defs_of_instr(ctx->ssa, ssa_op); + zend_ssa_remove_instr(ctx->ssa, opline, ssa_op); + + if (free_var >= 0) { + opline->opcode = ZEND_FREE; + opline->op1.var = (uintptr_t) ZEND_CALL_VAR_NUM(NULL, ssa->vars[free_var].var); + opline->op1_type = free_var_type; + + ssa_op->op1_use = free_var; + ssa_op->op1_use_chain = ssa->vars[free_var].use_chain; + ssa->vars[free_var].use_chain = ssa_op - ssa->ops; + return 0; + } + return 1; +} + +// TODO Move this somewhere else (CFG simplification?) +static int simplify_jumps(zend_ssa *ssa, zend_op_array *op_array) { + int removed_ops = 0; + zend_basic_block *block; + FOREACH_BLOCK(block) { + int block_num = block - ssa->cfg.blocks; + zend_op *opline = &op_array->opcodes[block->start + block->len - 1]; + zend_ssa_op *ssa_op = &ssa->ops[block->start + block->len - 1]; + zval *op1; + + if (block->len == 0) { + continue; + } + + /* Convert jump-and-set into jump if result is not used */ + switch (opline->opcode) { + case ZEND_JMPZ_EX: + ZEND_ASSERT(ssa_op->result_def >= 0); + if (ssa->vars[ssa_op->result_def].use_chain < 0 + && ssa->vars[ssa_op->result_def].phi_use_chain == NULL) { + opline->opcode = ZEND_JMPZ; + opline->result_type = IS_UNUSED; + zend_ssa_remove_result_def(ssa, ssa_op); + } + break; + case ZEND_JMPNZ_EX: + case ZEND_JMP_SET: + ZEND_ASSERT(ssa_op->result_def >= 0); + if (ssa->vars[ssa_op->result_def].use_chain < 0 + && ssa->vars[ssa_op->result_def].phi_use_chain == NULL) { + opline->opcode = ZEND_JMPNZ; + opline->result_type = IS_UNUSED; + zend_ssa_remove_result_def(ssa, ssa_op); + } + break; + } + + /* Convert jump-and-set to QM_ASSIGN/BOOL if the "else" branch is not taken. */ + switch (opline->opcode) { + case ZEND_JMPZ_EX: + case ZEND_JMPNZ_EX: + if (block->successors_count == 1 && block->successors[0] != block_num + 1) { + opline->opcode = ZEND_BOOL; + } + break; + case ZEND_JMP_SET: + case ZEND_COALESCE: + if (block->successors_count == 1 && block->successors[0] != block_num + 1) { + opline->opcode = ZEND_QM_ASSIGN; + } + break; + } + + if (opline->op1_type != IS_CONST) { + continue; + } + + /* Convert constant conditional jump to unconditional jump */ + op1 = &ZEND_OP1_LITERAL(opline); + switch (opline->opcode) { + case ZEND_JMPZ: + if (!zend_is_true(op1)) { + literal_dtor(op1); + opline->op1_type = IS_UNUSED; + opline->op1.num = opline->op2.num; + opline->opcode = ZEND_JMP; + } else { + MAKE_NOP(opline); + removed_ops++; + } + break; + case ZEND_JMPNZ: + if (zend_is_true(op1)) { + literal_dtor(op1); + opline->op1_type = IS_UNUSED; + opline->op1.num = opline->op2.num; + opline->opcode = ZEND_JMP; + } else { + MAKE_NOP(opline); + removed_ops++; + } + break; + case ZEND_COALESCE: + ZEND_ASSERT(ssa_op->result_def >= 0); + if (ssa->vars[ssa_op->result_def].use_chain >= 0 + || ssa->vars[ssa_op->result_def].phi_use_chain != NULL) { + break; + } + + zend_ssa_remove_result_def(ssa, ssa_op); + if (Z_TYPE_P(op1) != IS_NULL) { + literal_dtor(op1); + opline->op1_type = IS_UNUSED; + opline->op1.num = opline->op2.num; + opline->opcode = ZEND_JMP; + opline->result_type = IS_UNUSED; + } else { + MAKE_NOP(opline); + removed_ops++; + } + break; + } + } FOREACH_BLOCK_END(); + return removed_ops; +} + +static inline int get_common_phi_source(zend_ssa *ssa, zend_ssa_phi *phi) { + int common_source = -1; + int source; + FOREACH_PHI_SOURCE(phi, source) { + if (common_source == -1) { + common_source = source; + } else if (common_source != source && source != phi->ssa_var) { + return -1; + } + } FOREACH_PHI_SOURCE_END(); + ZEND_ASSERT(common_source != -1); + return common_source; +} + +static void try_remove_trivial_phi(context *ctx, zend_ssa_phi *phi) { + zend_ssa *ssa = ctx->ssa; + if (phi->pi < 0) { + /* Phi assignment with identical source operands */ + int common_source = get_common_phi_source(ssa, phi); + if (common_source >= 0) { + zend_ssa_rename_var_uses(ssa, phi->ssa_var, common_source, 1); + zend_ssa_remove_phi(ssa, phi); + } + } else { + /* Pi assignment that is only used in Phi/Pi assignments */ + // TODO What if we want to rerun type inference after DCE? Maybe separate this? + /*ZEND_ASSERT(phi->sources[0] != -1); + if (ssa->vars[phi->ssa_var].use_chain < 0) { + zend_ssa_rename_var_uses_keep_types(ssa, phi->ssa_var, phi->sources[0], 1); + zend_ssa_remove_phi(ssa, phi); + }*/ + } +} + +static inline zend_bool may_break_varargs(const zend_op_array *op_array, const zend_ssa *ssa, const zend_ssa_op *ssa_op) { + if (ssa_op->op1_def >= 0 + && ssa->vars[ssa_op->op1_def].var < op_array->num_args) { + return 1; + } + if (ssa_op->op2_def >= 0 + && ssa->vars[ssa_op->op2_def].var < op_array->num_args) { + return 1; + } + if (ssa_op->result_def >= 0 + && ssa->vars[ssa_op->result_def].var < op_array->num_args) { + return 1; + } + return 0; +} + +int dce_optimize_op_array(zend_op_array *op_array, zend_ssa *ssa, zend_bool reorder_dtor_effects) { + int i; + zend_ssa_phi *phi; + int removed_ops = 0; + + /* DCE of CV operations that changes arguments may affect vararg functions. */ + zend_bool has_varargs = ssa->cfg.vararg; + + context ctx; + ctx.ssa = ssa; + ctx.op_array = op_array; + ctx.reorder_dtor_effects = reorder_dtor_effects; + + /* We have no dedicated phi vector, so we use the whole ssa var vector instead */ + ctx.instr_worklist_len = zend_bitset_len(op_array->last); + ctx.instr_worklist = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len); + memset(ctx.instr_worklist, 0, sizeof(zend_ulong) * ctx.instr_worklist_len); + ctx.phi_worklist_len = zend_bitset_len(ssa->vars_count); + ctx.phi_worklist = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len); + memset(ctx.phi_worklist, 0, sizeof(zend_ulong) * ctx.phi_worklist_len); + ctx.phi_worklist_no_val = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len); + memset(ctx.phi_worklist_no_val, 0, sizeof(zend_ulong) * ctx.phi_worklist_len); + + /* Optimistically assume all instructions and phis to be dead */ + ctx.instr_dead = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len); + memset(ctx.instr_dead, 0, sizeof(zend_ulong) * ctx.instr_worklist_len); + ctx.phi_dead = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len); + memset(ctx.phi_dead, 0xff, sizeof(zend_ulong) * ctx.phi_worklist_len); + + /* Mark reacable instruction without side effects as dead */ + int b = ssa->cfg.blocks_count; + while (b > 0) { + b--; + zend_basic_block *block = &ssa->cfg.blocks[b]; + if (!(block->flags & ZEND_BB_REACHABLE)) { + continue; + } + i = block->start + block->len; + while (i > block->start) { + i--; + + if (zend_bitset_in(ctx.instr_worklist, i)) { + zend_bitset_excl(ctx.instr_worklist, i); + add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 0); + } else if (may_have_side_effects(op_array, ssa, &op_array->opcodes[i], &ssa->ops[i], ctx.reorder_dtor_effects) + || zend_may_throw(&op_array->opcodes[i], op_array, ssa) + || (has_varargs && may_break_varargs(op_array, ssa, &ssa->ops[i]))) { + add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 0); + } else { + zend_bitset_incl(ctx.instr_dead, i); + } + + } + } + + /* Propagate liveness backwards to all definitions of used vars */ + while (!zend_bitset_empty(ctx.instr_worklist, ctx.instr_worklist_len) + || !zend_bitset_empty(ctx.phi_worklist, ctx.phi_worklist_len)) { + while ((i = zend_bitset_pop_first(ctx.instr_worklist, ctx.instr_worklist_len)) >= 0) { + zend_bitset_excl(ctx.instr_dead, i); + add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 1); + } + while ((i = zend_bitset_pop_first(ctx.phi_worklist, ctx.phi_worklist_len)) >= 0) { + zend_bitset_excl(ctx.phi_dead, i); + zend_bitset_excl(ctx.phi_worklist_no_val, i); + add_phi_sources_to_worklists(&ctx, ssa->vars[i].definition_phi, 1); + } + } + + /* Eliminate dead instructions */ + ZEND_BITSET_FOREACH(ctx.instr_dead, ctx.instr_worklist_len, i) { + removed_ops += dce_instr(&ctx, &op_array->opcodes[i], &ssa->ops[i]); + } ZEND_BITSET_FOREACH_END(); + + /* Improper uses don't count as "uses" for the purpose of instruction elimination, + * but we have to retain phis defining them. + * Propagate this information backwards, marking any phi with an improperly used + * target as non-dead. */ + while ((i = zend_bitset_pop_first(ctx.phi_worklist_no_val, ctx.phi_worklist_len)) >= 0) { + zend_ssa_phi *phi = ssa->vars[i].definition_phi; + int source; + zend_bitset_excl(ctx.phi_dead, i); + FOREACH_PHI_SOURCE(phi, source) { + add_to_phi_worklist_no_val(&ctx, source); + } FOREACH_PHI_SOURCE_END(); + } + + /* Now collect the actually dead phis */ + FOREACH_PHI(phi) { + if (zend_bitset_in(ctx.phi_dead, phi->ssa_var)) { + zend_ssa_remove_uses_of_var(ssa, phi->ssa_var); + zend_ssa_remove_phi(ssa, phi); + } else { + /* Remove trivial phis (phis with identical source operands) */ + try_remove_trivial_phi(&ctx, phi); + } + } FOREACH_PHI_END(); + + removed_ops += simplify_jumps(ssa, op_array); + + return removed_ops; +} diff --git a/ext/opcache/Optimizer/dfa_pass.c b/ext/opcache/Optimizer/dfa_pass.c index 1b589eed45..642e0d3ead 100644 --- a/ext/opcache/Optimizer/dfa_pass.c +++ b/ext/opcache/Optimizer/dfa_pass.c @@ -31,6 +31,14 @@ #include "zend_inference.h" #include "zend_dump.h" +#ifndef ZEND_DEBUG_DFA +# define ZEND_DEBUG_DFA ZEND_DEBUG +#endif + +#if ZEND_DEBUG_DFA +# include "ssa_integrity.c" +#endif + int zend_dfa_analyze_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa, uint32_t *flags) { uint32_t build_flags; @@ -87,7 +95,7 @@ int zend_dfa_analyze_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, } if (ctx->debug_level & ZEND_DUMP_DFA_SSA) { - zend_dump_op_array(op_array, ZEND_DUMP_SSA, "before dfa pass", ssa); + zend_dump_op_array(op_array, ZEND_DUMP_SSA, "dfa ssa", ssa); } @@ -153,6 +161,7 @@ static void zend_ssa_remove_nops(zend_op_array *op_array, zend_ssa *ssa) if (i != target) { op_array->opcodes[target] = op_array->opcodes[i]; ssa->ops[target] = ssa->ops[i]; + ssa->cfg.map[target] = b - blocks; } target++; } @@ -171,6 +180,9 @@ static void zend_ssa_remove_nops(zend_op_array *op_array, zend_ssa *ssa) new_opline = op_array->opcodes + target - 1; zend_optimizer_migrate_jump(op_array, new_opline, opline); } + } else { + b->start = target; + b->len = 0; } } @@ -319,7 +331,126 @@ static zend_bool opline_supports_assign_contraction( return 1; } -void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa) +int zend_dfa_optimize_calls(zend_op_array *op_array, zend_ssa *ssa) +{ + zend_func_info *func_info = ZEND_FUNC_INFO(op_array); + int removed_ops = 0; + + if (func_info->callee_info) { + zend_call_info *call_info = func_info->callee_info; + + do { + if (call_info->caller_call_opline->opcode == ZEND_DO_ICALL + && call_info->callee_func + && ZSTR_LEN(call_info->callee_func->common.function_name) == sizeof("in_array")-1 + && memcmp(ZSTR_VAL(call_info->callee_func->common.function_name), "in_array", sizeof("in_array")-1) == 0 + && (call_info->caller_init_opline->extended_value == 2 + || (call_info->caller_init_opline->extended_value == 3 + && (call_info->caller_call_opline - 1)->opcode == ZEND_SEND_VAL + && (call_info->caller_call_opline - 1)->op1_type == IS_CONST))) { + + zend_op *send_array; + zend_op *send_needly; + zend_bool strict = 0; + + if (call_info->caller_init_opline->extended_value == 2) { + send_array = call_info->caller_call_opline - 1; + send_needly = call_info->caller_call_opline - 2; + } else { + if (zend_is_true(CT_CONSTANT_EX(op_array, (call_info->caller_call_opline - 1)->op1.constant))) { + strict = 1; + } + send_array = call_info->caller_call_opline - 2; + send_needly = call_info->caller_call_opline - 3; + } + + if (send_array->opcode == ZEND_SEND_VAL + && send_array->op1_type == IS_CONST + && Z_TYPE_P(CT_CONSTANT_EX(op_array, send_array->op1.constant)) == IS_ARRAY + && (send_needly->opcode == ZEND_SEND_VAL + || send_needly->opcode == ZEND_SEND_VAR) + ) { + int ok = 1; + + HashTable *src = Z_ARRVAL_P(CT_CONSTANT_EX(op_array, send_array->op1.constant)); + HashTable *dst; + zval *val, tmp; + zend_ulong idx; + + ZVAL_TRUE(&tmp); + dst = emalloc(sizeof(HashTable)); + zend_hash_init(dst, zend_hash_num_elements(src), NULL, ZVAL_PTR_DTOR, 0); + if (strict) { + ZEND_HASH_FOREACH_VAL(src, val) { + if (Z_TYPE_P(val) == IS_STRING) { + zend_hash_add(dst, Z_STR_P(val), &tmp); + } else if (Z_TYPE_P(val) == IS_LONG) { + zend_hash_index_add(dst, Z_LVAL_P(val), &tmp); + } else { + zend_array_destroy(dst); + ok = 0; + break; + } + } ZEND_HASH_FOREACH_END(); + } else { + ZEND_HASH_FOREACH_VAL(src, val) { + if (Z_TYPE_P(val) != IS_STRING || ZEND_HANDLE_NUMERIC(Z_STR_P(val), idx)) { + zend_array_destroy(dst); + ok = 0; + break; + } + zend_hash_add(dst, Z_STR_P(val), &tmp); + } ZEND_HASH_FOREACH_END(); + } + + if (ok) { + uint32_t op_num = send_needly - op_array->opcodes; + zend_ssa_op *ssa_op = ssa->ops + op_num; + + if (ssa_op->op1_use >= 0) { + /* Reconstruct SSA */ + int var_num = ssa_op->op1_use; + zend_ssa_var *var = ssa->vars + var_num; + + ZEND_ASSERT(ssa_op->op1_def < 0); + zend_ssa_unlink_use_chain(ssa, op_num, ssa_op->op1_use); + ssa_op->op1_use = -1; + ssa_op->op1_use_chain = -1; + op_num = call_info->caller_call_opline - op_array->opcodes; + ssa_op = ssa->ops + op_num; + ssa_op->op1_use = var_num; + ssa_op->op1_use_chain = var->use_chain; + var->use_chain = op_num; + } + + ZVAL_ARR(&tmp, dst); + + /* Update opcode */ + call_info->caller_call_opline->opcode = ZEND_IN_ARRAY; + call_info->caller_call_opline->extended_value = strict; + call_info->caller_call_opline->op1_type = send_needly->op1_type; + call_info->caller_call_opline->op1.num = send_needly->op1.num; + call_info->caller_call_opline->op2_type = IS_CONST; + call_info->caller_call_opline->op2.constant = zend_optimizer_add_literal(op_array, &tmp); + if (call_info->caller_init_opline->extended_value == 3) { + MAKE_NOP(call_info->caller_call_opline - 1); + } + MAKE_NOP(call_info->caller_init_opline); + MAKE_NOP(send_needly); + MAKE_NOP(send_array); + removed_ops++; + + } + } + } + call_info = call_info->next_callee; + } while (call_info); + } + + return removed_ops; +} + +void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa, zend_call_info **call_map) { if (ctx->debug_level & ZEND_DUMP_BEFORE_DFA_PASS) { zend_dump_op_array(op_array, ZEND_DUMP_SSA, "before dfa pass", ssa); @@ -332,6 +463,38 @@ void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx zend_op *opline; zval tmp; + if (ZEND_OPTIMIZER_PASS_8 & ctx->optimization_level) { + if (sccp_optimize_op_array(ctx, op_array, ssa, call_map)) { + remove_nops = 1; + } +#if ZEND_DEBUG_DFA + ssa_verify_integrity(op_array, ssa, "after sccp"); +#endif + if (ZEND_FUNC_INFO(op_array)) { + if (zend_dfa_optimize_calls(op_array, ssa)) { + remove_nops = 1; + } + } + if (ctx->debug_level & ZEND_DUMP_AFTER_PASS_8) { + zend_dump_op_array(op_array, ZEND_DUMP_SSA, "after sccp pass", ssa); + } +#if ZEND_DEBUG_DFA + ssa_verify_integrity(op_array, ssa, "after calls"); +#endif + } + + if (ZEND_OPTIMIZER_PASS_14 & ctx->optimization_level) { + if (dce_optimize_op_array(op_array, ssa, 0)) { + remove_nops = 1; + } + if (ctx->debug_level & ZEND_DUMP_AFTER_PASS_14) { + zend_dump_op_array(op_array, ZEND_DUMP_SSA, "after dce pass", ssa); + } +#if ZEND_DEBUG_DFA + ssa_verify_integrity(op_array, ssa, "after dce"); +#endif + } + for (v = op_array->last_var; v < ssa->vars_count; v++) { op_1 = ssa->vars[v].definition; @@ -470,24 +633,28 @@ void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx // op_1: ASSIGN #orig_var.CV [undef,scalar] -> #v.CV, CONST|TMPVAR => QM_ASSIGN v.CV, CONST|TMPVAR - if (zend_ssa_unlink_use_chain(ssa, op_1, orig_var)) { - /* Reconstruct SSA */ - ssa->ops[op_1].result_def = v; - ssa->ops[op_1].op1_def = -1; - ssa->ops[op_1].op1_use = ssa->ops[op_1].op2_use; - ssa->ops[op_1].op1_use_chain = ssa->ops[op_1].op2_use_chain; - ssa->ops[op_1].op2_use = -1; - ssa->ops[op_1].op2_use_chain = -1; - - /* Update opcode */ - opline->result_type = opline->op1_type; - opline->result.var = opline->op1.var; - opline->op1_type = opline->op2_type; - opline->op1.var = opline->op2.var; - opline->op2_type = IS_UNUSED; - opline->op2.var = 0; - opline->opcode = ZEND_QM_ASSIGN; + if (ssa->ops[op_1].op1_use != ssa->ops[op_1].op2_use) { + zend_ssa_unlink_use_chain(ssa, op_1, orig_var); + } else { + ssa->ops[op_1].op2_use_chain = ssa->ops[op_1].op1_use_chain; } + + /* Reconstruct SSA */ + ssa->ops[op_1].result_def = v; + ssa->ops[op_1].op1_def = -1; + ssa->ops[op_1].op1_use = ssa->ops[op_1].op2_use; + ssa->ops[op_1].op1_use_chain = ssa->ops[op_1].op2_use_chain; + ssa->ops[op_1].op2_use = -1; + ssa->ops[op_1].op2_use_chain = -1; + + /* Update opcode */ + opline->result_type = opline->op1_type; + opline->result.var = opline->op1.var; + opline->op1_type = opline->op2_type; + opline->op1.var = opline->op2.var; + opline->op2_type = IS_UNUSED; + opline->op2.var = 0; + opline->opcode = ZEND_QM_ASSIGN; } } @@ -577,8 +744,15 @@ void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx } } +#if ZEND_DEBUG_DFA + ssa_verify_integrity(op_array, ssa, "after dfa"); +#endif + if (remove_nops) { zend_ssa_remove_nops(op_array, ssa); +#if ZEND_DEBUG_DFA + ssa_verify_integrity(op_array, ssa, "after nop"); +#endif } } @@ -598,7 +772,7 @@ void zend_optimize_dfa(zend_op_array *op_array, zend_optimizer_ctx *ctx) return; } - zend_dfa_optimize_op_array(op_array, ctx, &ssa); + zend_dfa_optimize_op_array(op_array, ctx, &ssa, NULL); /* Destroy SSA */ zend_arena_release(&ctx->arena, checkpoint); diff --git a/ext/opcache/Optimizer/sccp.c b/ext/opcache/Optimizer/sccp.c new file mode 100644 index 0000000000..326603a0e4 --- /dev/null +++ b/ext/opcache/Optimizer/sccp.c @@ -0,0 +1,1445 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, SCCP - Sparse Conditional Constant Propagation | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Nikita Popov | + +----------------------------------------------------------------------+ +*/ + +#include "php.h" +#include "zend_type_info.h" +#include "ZendAccelerator.h" +#include "Optimizer/zend_optimizer_internal.h" +#include "Optimizer/zend_call_graph.h" +#include "Optimizer/scdf.h" +#include "Optimizer/zend_dump.h" +#include "ext/standard/php_string.h" + +/* This implements sparse conditional constant propagation (SCCP) based on the SCDF framework. The + * used value lattice is defined as follows: + * + * BOT < {constant values} < TOP + * + * TOP indicates an underdefined value, i.e. that we do not yet know the value of variable. + * BOT indicates an overdefined value, i.e. that we know the variable to be non-constant. + * + * All variables are optimistically initialized to TOP, apart from the implicit variables defined + * at the start of the first block. Note that variables that MAY_BE_REF are *not* initialized to + * BOT. We rely on the fact that any operation resulting in a reference will produce a BOT anyway. + * This is better because such operations might never be reached due to the conditional nature of + * the algorithm. + * + * The meet operation for phi functions is defined as follows: + * BOT + any = BOT + * TOP + any = any + * C_i + C_i = C_i (i.e. two equal constants) + * C_i + C_j = BOT (i.e. two different constants) + * + * When evaluating instructions TOP and BOT are handled as follows: + * a) If any operand is BOT, the result is BOT. The main exception to this is op1 of ASSIGN, which + * is ignored. However, if the op1 MAY_BE_REF we do have to propagate the BOT. + * b) Otherwise, if the instruction can never be evaluated (either in general, or with the + * specific modifiers) the result is BOT. + * c) Otherwise, if any operand is TOP, the result is TOP. + * d) Otherwise (at this point all operands are known and constant), if we can compute the result + * for these specific constants (without throwing notices or similar) then that is the result. + * e) Otherwise the result is BOT. + * + * It is sometimes possible to determine a result even if one argument is TOP / BOT, e.g. for things + * like BOT*0. Right now we don't bother with this -- the only thing that is done is evaluating + * TYPE_CHECKS based on the type information. + * + * Feasible successors for conditional branches are determined as follows: + * a) If we don't support the branch type or branch on BOT, all successors are feasible. + * b) Otherwise, if we branch on TOP none of the successors are feasible. + * c) Otherwise (we branch on a constant), the feasible successors are marked based on the constant + * (usually only one successor will be feasible). + */ + +#if 0 +#define SCP_DEBUG(...) php_printf(__VA_ARGS__) +#else +#define SCP_DEBUG(...) +#endif + +typedef struct _sccp_ctx { + scdf_ctx scdf; + zend_call_info **call_map; + zval *values; + zval top; + zval bot; +} sccp_ctx; + +#define TOP ((zend_uchar)-1) +#define BOT ((zend_uchar)-2) +#define IS_TOP(zv) (Z_TYPE_P(zv) == TOP) +#define IS_BOT(zv) (Z_TYPE_P(zv) == BOT) + +#define MAKE_TOP(zv) (Z_TYPE_INFO_P(zv) = TOP) +#define MAKE_BOT(zv) (Z_TYPE_INFO_P(zv) = BOT) + +static inline zend_bool value_known(zval *zv) { + return !IS_TOP(zv) && !IS_BOT(zv); +} + +/* Sets new value for variable and ensures that it is lower or equal + * the previous one in the constant propagation lattice. */ +static void set_value(scdf_ctx *scdf, sccp_ctx *ctx, int var, zval *new) { + zval *value = &ctx->values[var]; + if (IS_BOT(value) || IS_TOP(new)) { + return; + } + + if (IS_BOT(new)) { + SCP_DEBUG("Lowering var %d to BOT\n", var); + } else { + SCP_DEBUG("Lowering var %d to %Z\n", var, new); + } + + if (IS_TOP(value) || IS_BOT(new)) { + zval_ptr_dtor_nogc(value); + ZVAL_COPY(value, new); + scdf_add_to_worklist(scdf, var); + return; + } + +#if ZEND_DEBUG + ZEND_ASSERT(zend_is_identical(value, new)); +#endif +} + +static zval *get_op1_value(sccp_ctx *ctx, zend_op *opline, zend_ssa_op *ssa_op) { + if (opline->op1_type == IS_CONST) { + return CT_CONSTANT_EX(ctx->scdf.op_array, opline->op1.constant); + } else if (ssa_op->op1_use != -1) { + return &ctx->values[ssa_op->op1_use]; + } else { + return NULL; + } +} + +static zval *get_op2_value(sccp_ctx *ctx, zend_op *opline, zend_ssa_op *ssa_op) { + if (opline->op2_type == IS_CONST) { + return CT_CONSTANT_EX(ctx->scdf.op_array, opline->op2.constant); + } else if (ssa_op->op2_use != -1) { + return &ctx->values[ssa_op->op2_use]; + } else { + return NULL; + } +} + +static zend_bool can_replace_op1( + const zend_op_array *op_array, zend_op *opline, zend_ssa_op *ssa_op) { + switch (opline->opcode) { + case ZEND_PRE_INC: + case ZEND_PRE_DEC: + case ZEND_PRE_INC_OBJ: + case ZEND_PRE_DEC_OBJ: + case ZEND_POST_INC: + case ZEND_POST_DEC: + case ZEND_POST_INC_OBJ: + case ZEND_POST_DEC_OBJ: + case ZEND_ASSIGN: + case ZEND_ASSIGN_REF: + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_OBJ: + case ZEND_ASSIGN_ADD: + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + case ZEND_ASSIGN_CONCAT: + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + case ZEND_ASSIGN_POW: + case ZEND_FETCH_DIM_W: + case ZEND_FETCH_DIM_RW: + case ZEND_FETCH_DIM_UNSET: + case ZEND_FETCH_DIM_FUNC_ARG: + case ZEND_FETCH_OBJ_W: + case ZEND_FETCH_OBJ_RW: + case ZEND_FETCH_OBJ_UNSET: + case ZEND_FETCH_OBJ_FUNC_ARG: + case ZEND_UNSET_DIM: + case ZEND_UNSET_OBJ: + case ZEND_SEND_REF: + case ZEND_SEND_VAR_EX: + case ZEND_SEND_UNPACK: + case ZEND_SEND_ARRAY: + case ZEND_SEND_USER: + case ZEND_FE_RESET_RW: + return 0; + /* Do not accept CONST */ + case ZEND_VERIFY_ABSTRACT_CLASS: + case ZEND_ADD_INTERFACE: + case ZEND_ADD_TRAIT: + case ZEND_BIND_TRAITS: + case ZEND_ROPE_ADD: + case ZEND_ROPE_END: + case ZEND_BIND_STATIC: + case ZEND_BIND_GLOBAL: + case ZEND_MAKE_REF: + return 0; + case ZEND_UNSET_VAR: + case ZEND_ISSET_ISEMPTY_VAR: + /* CV has special meaning here - cannot simply be replaced */ + return (opline->extended_value & ZEND_QUICK_SET) == 0; + case ZEND_INIT_ARRAY: + case ZEND_ADD_ARRAY_ELEMENT: + return !(opline->extended_value & ZEND_ARRAY_ELEMENT_REF); + case ZEND_YIELD: + return !(op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE); + case ZEND_VERIFY_RETURN_TYPE: + // TODO: This would require a non-local change ??? + return 0; + default: + if (ssa_op->op1_def != -1) { + ZEND_ASSERT(0); + return 0; + } + } + + return 1; +} + +static zend_bool can_replace_op2( + const zend_op_array *op_array, zend_op *opline, zend_ssa_op *ssa_op) { + switch (opline->opcode) { + /* Do not accept CONST */ + case ZEND_DECLARE_INHERITED_CLASS: + case ZEND_DECLARE_INHERITED_CLASS_DELAYED: + case ZEND_DECLARE_ANON_INHERITED_CLASS: + case ZEND_BIND_LEXICAL: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: + return 0; + } + return 1; +} + +static zend_bool try_replace_op1( + sccp_ctx *ctx, zend_op *opline, zend_ssa_op *ssa_op, int var, zval *value) { + if (ssa_op->op1_use == var && can_replace_op1(ctx->scdf.op_array, opline, ssa_op)) { + zval zv; + ZVAL_COPY(&zv, value); + if (zend_optimizer_update_op1_const(ctx->scdf.op_array, opline, &zv)) { + return 1; + } else { + // TODO: check the following special cases ??? + switch (opline->opcode) { + case ZEND_FETCH_LIST: + case ZEND_CASE: + case ZEND_SWITCH_STRING: + case ZEND_SWITCH_LONG: + if (Z_TYPE(zv) == IS_STRING) { + zend_string_hash_val(Z_STR(zv)); + } + opline->op1.constant = zend_optimizer_add_literal(ctx->scdf.op_array, &zv); + opline->op1_type = IS_CONST; + return 1; + } + zval_ptr_dtor_nogc(&zv); + } + } + return 0; +} + +static zend_bool try_replace_op2( + sccp_ctx *ctx, zend_op *opline, zend_ssa_op *ssa_op, int var, zval *value) { + if (ssa_op->op2_use == var && can_replace_op2(ctx->scdf.op_array, opline, ssa_op)) { + zval zv; + ZVAL_COPY(&zv, value); + if (zend_optimizer_update_op2_const(ctx->scdf.op_array, opline, &zv)) { + return 1; + } else { + zval_ptr_dtor_nogc(&zv); + } + } + return 0; +} + +static inline int zval_to_string_offset(zend_long *result, zval *op) { + switch (Z_TYPE_P(op)) { + case IS_LONG: + *result = Z_LVAL_P(op); + return SUCCESS; + case IS_STRING: + if (IS_LONG == is_numeric_string( + Z_STRVAL_P(op), Z_STRLEN_P(op), result, NULL, 0)) { + return SUCCESS; + } + return FAILURE; + default: + return FAILURE; + } +} + +static inline int fetch_array_elem(zval **result, zval *op1, zval *op2) { + switch (Z_TYPE_P(op2)) { + case IS_NULL: + *result = zend_hash_find(Z_ARR_P(op1), ZSTR_EMPTY_ALLOC()); + return SUCCESS; + case IS_FALSE: + *result = zend_hash_index_find(Z_ARR_P(op1), 0); + return SUCCESS; + case IS_TRUE: + *result = zend_hash_index_find(Z_ARR_P(op1), 1); + return SUCCESS; + case IS_LONG: + *result = zend_hash_index_find(Z_ARR_P(op1), Z_LVAL_P(op2)); + return SUCCESS; + case IS_DOUBLE: + *result = zend_hash_index_find(Z_ARR_P(op1), zend_dval_to_lval(Z_DVAL_P(op2))); + return SUCCESS; + case IS_STRING: + *result = zend_symtable_find(Z_ARR_P(op1), Z_STR_P(op2)); + return SUCCESS; + default: + return FAILURE; + } +} + +static inline int ct_eval_fetch_dim(zval *result, zval *op1, zval *op2, int support_strings) { + if (Z_TYPE_P(op1) == IS_ARRAY) { + zval *value; + if (fetch_array_elem(&value, op1, op2) == SUCCESS && value) { + ZVAL_COPY(result, value); + return SUCCESS; + } + } else if (support_strings && Z_TYPE_P(op1) == IS_STRING) { + zend_long index; + if (zval_to_string_offset(&index, op2) == FAILURE) { + return FAILURE; + } + if (index >= 0 && index < Z_STRLEN_P(op1)) { + ZVAL_STR(result, zend_string_init(&Z_STRVAL_P(op1)[index], 1, 0)); + return SUCCESS; + } + } + return FAILURE; +} + +static inline int ct_eval_isset_dim(zval *result, uint32_t extended_value, zval *op1, zval *op2) { + if (Z_TYPE_P(op1) == IS_ARRAY) { + zval *value; + if (fetch_array_elem(&value, op1, op2) == FAILURE) { + return FAILURE; + } + if (extended_value & ZEND_ISSET) { + ZVAL_BOOL(result, value && Z_TYPE_P(value) != IS_NULL); + } else { + ZEND_ASSERT(extended_value & ZEND_ISEMPTY); + ZVAL_BOOL(result, !value || !zend_is_true(value)); + } + return SUCCESS; + } else if (Z_TYPE_P(op1) == IS_STRING) { + // TODO + return FAILURE; + } else { + ZVAL_BOOL(result, extended_value != ZEND_ISSET); + return SUCCESS; + } +} + +static inline int ct_eval_add_array_elem(zval *result, zval *value, zval *key) { + if (!key) { + if ((value = zend_hash_next_index_insert(Z_ARR_P(result), value))) { + Z_TRY_ADDREF_P(value); + return SUCCESS; + } + return FAILURE; + } + + switch (Z_TYPE_P(key)) { + case IS_NULL: + value = zend_hash_update(Z_ARR_P(result), ZSTR_EMPTY_ALLOC(), value); + break; + case IS_FALSE: + value = zend_hash_index_update(Z_ARR_P(result), 0, value); + break; + case IS_TRUE: + value = zend_hash_index_update(Z_ARR_P(result), 1, value); + break; + case IS_LONG: + value = zend_hash_index_update(Z_ARR_P(result), Z_LVAL_P(key), value); + break; + case IS_DOUBLE: + value = zend_hash_index_update( + Z_ARR_P(result), zend_dval_to_lval(Z_DVAL_P(key)), value); + break; + case IS_STRING: + value = zend_symtable_update(Z_ARR_P(result), Z_STR_P(key), value); + break; + default: + return FAILURE; + } + + Z_TRY_ADDREF_P(value); + return SUCCESS; +} + +static inline int ct_eval_assign_dim(zval *result, zval *value, zval *key) { + switch (Z_TYPE_P(result)) { + case IS_NULL: + case IS_FALSE: + array_init(result); + /* break missing intentionally */ + case IS_ARRAY: + return ct_eval_add_array_elem(result, value, key); + case IS_STRING: + // TODO Before enabling this case, make sure ARRAY_DIM result op is correct +#if 0 + zend_long index; + zend_string *new_str, *value_str; + if (!key || Z_TYPE_P(value) == IS_ARRAY + || zval_to_string_offset(&index, key) == FAILURE || index < 0) { + return FAILURE; + } + + if (index >= Z_STRLEN_P(result)) { + new_str = zend_string_alloc(index + 1, 0); + memcpy(ZSTR_VAL(new_str), Z_STRVAL_P(result), Z_STRLEN_P(result)); + memset(ZSTR_VAL(new_str) + Z_STRLEN_P(result), ' ', index - Z_STRLEN_P(result)); + ZSTR_VAL(new_str)[index + 1] = 0; + } else { + new_str = zend_string_init(Z_STRVAL_P(result), Z_STRLEN_P(result), 0); + } + + value_str = zval_get_string(value); + ZVAL_STR(result, new_str); + Z_STRVAL_P(result)[index] = ZSTR_VAL(value_str)[0]; + zend_string_release(value_str); +#endif + return FAILURE; + default: + return FAILURE; + } +} + +static inline int ct_eval_incdec(zval *result, zend_uchar opcode, zval *op1) { + ZVAL_COPY(result, op1); + if (opcode == ZEND_PRE_INC || opcode == ZEND_POST_INC) { + increment_function(result); + } else { + decrement_function(result); + } + return SUCCESS; +} + +static inline int ct_eval_isset_isempty(zval *result, uint32_t extended_value, zval *op1) { + if (!(extended_value & ZEND_QUICK_SET)) { + return FAILURE; + } + + if (extended_value & ZEND_ISSET) { + ZVAL_BOOL(result, Z_TYPE_P(op1) != IS_NULL); + } else { + ZEND_ASSERT(extended_value & ZEND_ISEMPTY); + ZVAL_BOOL(result, !zend_is_true(op1)); + } + return SUCCESS; +} + +static inline void ct_eval_type_check(zval *result, uint32_t type, zval *op1) { + if (type == _IS_BOOL) { + ZVAL_BOOL(result, Z_TYPE_P(op1) == IS_TRUE || Z_TYPE_P(op1) == IS_FALSE); + } else { + ZVAL_BOOL(result, Z_TYPE_P(op1) == type); + } +} + +/* The functions chosen here are simple to implement and either likely to affect a branch, + * or just happened to be commonly used with constant operands in WP (need to test other + * applications as well, of course). */ +static inline int ct_eval_func_call( + zval *result, zend_string *name, uint32_t num_args, zval **args) { + uint32_t i; + zend_execute_data *execute_data; + zend_function *func; + int overflow; + + if (zend_string_equals_literal(name, "chr")) { + zend_long c; + if (num_args != 1 || Z_TYPE_P(args[0]) != IS_LONG) { + return FAILURE; + } + + c = Z_LVAL_P(args[0]) & 0xff; + ZVAL_INTERNED_STR(result, ZSTR_CHAR(c)); + return SUCCESS; + } else if (zend_string_equals_literal(name, "count")) { + if (num_args != 1 || Z_TYPE_P(args[0]) != IS_ARRAY) { + return FAILURE; + } + + ZVAL_LONG(result, zend_hash_num_elements(Z_ARRVAL_P(args[0]))); + return SUCCESS; + } else if (zend_string_equals_literal(name, "ini_get")) { + zend_ini_entry *ini_entry; + + if (num_args != 1 || Z_TYPE_P(args[0]) != IS_STRING) { + return FAILURE; + } + + ini_entry = zend_hash_find_ptr(EG(ini_directives), Z_STR_P(args[0])); + if (!ini_entry) { + ZVAL_FALSE(result); + } else if (ini_entry->modifiable != ZEND_INI_SYSTEM) { + return FAILURE; + } else if (ini_entry->value) { + ZVAL_STR_COPY(result, ini_entry->value); + } else { + ZVAL_EMPTY_STRING(result); + } + return SUCCESS; + } else if (zend_string_equals_literal(name, "in_array")) { + if (num_args != 2 || Z_TYPE_P(args[1]) != IS_ARRAY) { + return FAILURE; + } + /* pass */ + } else if (zend_string_equals_literal(name, "strpos")) { + if (num_args != 2 + || Z_TYPE_P(args[0]) != IS_STRING + || Z_TYPE_P(args[1]) != IS_STRING + || !Z_STRLEN_P(args[1])) { + return FAILURE; + } + /* pass */ + } else if (zend_string_equals_literal(name, "array_key_exists")) { + if (num_args != 2 || Z_TYPE_P(args[1]) != IS_ARRAY || + (Z_TYPE_P(args[0]) != IS_LONG && Z_TYPE_P(args[0]) != IS_STRING + && Z_TYPE_P(args[0]) != IS_NULL)) { + return FAILURE; + } + /* pass */ + } else if (zend_string_equals_literal(name, "trim") + || zend_string_equals_literal(name, "rtrim") + || zend_string_equals_literal(name, "ltrim")) { + if ((num_args < 1 || num_args > 2) || Z_TYPE_P(args[0]) != IS_STRING + || (num_args == 2 && Z_TYPE_P(args[1]) != IS_STRING)) { + return FAILURE; + } + /* pass */ + } else if (zend_string_equals_literal(name, "array_keys") + || zend_string_equals_literal(name, "array_values")) { + if (num_args != 1 || Z_TYPE_P(args[0]) != IS_ARRAY) { + return FAILURE; + } + /* pass */ + } else if (zend_string_equals_literal(name, "array_flip")) { + zval *entry; + + if (num_args != 1 || Z_TYPE_P(args[0]) != IS_ARRAY) { + return FAILURE; + } + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(args[0]), entry) { + if (Z_TYPE_P(entry) != IS_LONG && Z_TYPE_P(entry) != IS_STRING) { + return FAILURE; + } + } ZEND_HASH_FOREACH_END(); + /* pass */ + } else if (zend_string_equals_literal(name, "str_repeat")) { + if (num_args != 2 + || Z_TYPE_P(args[0]) != IS_STRING + || Z_TYPE_P(args[1]) != IS_LONG + || zend_safe_address(Z_STRLEN_P(args[0]), Z_LVAL_P(args[1]), 0, &overflow) > 64 * 1024 + || overflow) { + return FAILURE; + } + /* pass */ + } else if ((zend_string_equals_literal(name, "array_merge") + || zend_string_equals_literal(name, "array_replace") + || zend_string_equals_literal(name, "array_merge_recursive") + || zend_string_equals_literal(name, "array_merge_recursive") + || zend_string_equals_literal(name, "array_diff") + || zend_string_equals_literal(name, "array_diff_assoc") + || zend_string_equals_literal(name, "array_diff_key")) + && num_args > 0) { + for (i = 0; i < num_args; i++) { + if (Z_TYPE_P(args[i]) != IS_ARRAY) { + return FAILURE; + } + } + /* pass */ + } else if (zend_string_equals_literal(name, "implode")) { + zval *entry; + + if (!(num_args == 1 && Z_TYPE_P(args[0]) == IS_ARRAY) + && !(num_args == 2 && Z_TYPE_P(args[0]) == IS_STRING && Z_TYPE_P(args[1]) == IS_ARRAY) + && !(num_args == 2 && Z_TYPE_P(args[0]) == IS_ARRAY && Z_TYPE_P(args[1]) == IS_STRING)) { + return FAILURE; + } + + if (Z_TYPE_P(args[0]) == IS_ARRAY) { + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(args[0]), entry) { + if (Z_TYPE_P(entry) > IS_STRING) { + return FAILURE; + } + } ZEND_HASH_FOREACH_END(); + } else { + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(args[1]), entry) { + if (Z_TYPE_P(entry) > IS_STRING) { + return FAILURE; + } + } ZEND_HASH_FOREACH_END(); + } + /* pass */ + } else if (zend_string_equals_literal(name, "version_comapre")) { + if ((num_args != 2 && (num_args != 3 || Z_TYPE_P(args[2]) != IS_STRING)) + || Z_TYPE_P(args[0]) != IS_STRING + || Z_TYPE_P(args[1]) != IS_STRING) { + return FAILURE; + } + /* pass */ + } else { + return FAILURE; + } + + func = zend_hash_find_ptr(CG(function_table), name); + if (!func || func->type != ZEND_INTERNAL_FUNCTION) { + return FAILURE; + } + + execute_data = safe_emalloc(num_args, sizeof(zval), ZEND_CALL_FRAME_SLOT * sizeof(zval)); + memset(execute_data, 0, sizeof(zend_execute_data)); + EX(func) = func; + EX_NUM_ARGS() = num_args; + for (i = 0; i < num_args; i++) { + ZVAL_COPY(EX_VAR_NUM(i), args[i]); + } + func->internal_function.handler(execute_data, result); + for (i = 0; i < num_args; i++) { + zval_ptr_dtor_nogc(EX_VAR_NUM(i)); + } + efree(execute_data); + return SUCCESS; +} + +#define SET_RESULT(op, zv) do { \ + if (ssa_op->op##_def >= 0) { \ + set_value(scdf, ctx, ssa_op->op##_def, zv); \ + } \ +} while (0) +#define SET_RESULT_BOT(op) SET_RESULT(op, &ctx->bot) +#define SET_RESULT_TOP(op) SET_RESULT(op, &ctx->top) + +#define SKIP_IF_TOP(op) if (IS_TOP(op)) break; + +static void sccp_visit_instr(scdf_ctx *scdf, zend_op *opline, zend_ssa_op *ssa_op) { + sccp_ctx *ctx = (sccp_ctx *) scdf; + zval *op1, *op2, zv; /* zv is a temporary to hold result values */ + + op1 = get_op1_value(ctx, opline, ssa_op); + op2 = get_op2_value(ctx, opline, ssa_op); + + switch (opline->opcode) { + case ZEND_ASSIGN: + /* The value of op1 is irrelevant here, because we are overwriting it + * -- unless it can be a reference, in which case we propagate a BOT. */ + if (IS_BOT(op1) && (ctx->scdf.ssa->var_info[ssa_op->op1_use].type & MAY_BE_REF)) { + SET_RESULT_BOT(op1); + } else { + SET_RESULT(op1, op2); + } + + SET_RESULT(result, op2); + return; + case ZEND_TYPE_CHECK: + /* We may be able to evaluate TYPE_CHECK based on type inference info, + * even if we don't know the precise value. */ + if (!value_known(op1)) { + uint32_t type = ctx->scdf.ssa->var_info[ssa_op->op1_use].type; + uint32_t expected_type = opline->extended_value == _IS_BOOL + ? (MAY_BE_TRUE|MAY_BE_FALSE) : (1 << opline->extended_value); + if (!(type & expected_type) && !(type & MAY_BE_UNDEF)) { + ZVAL_FALSE(&zv); + SET_RESULT(result, &zv); + return; + } else if (!(type & ((MAY_BE_ANY|MAY_BE_UNDEF) - expected_type)) + && opline->extended_value != IS_RESOURCE) { + ZVAL_TRUE(&zv); + SET_RESULT(result, &zv); + return; + } + } + break; + case ZEND_ASSIGN_DIM: + /* If $a in $a[$b]=$c is UNDEF, treat it like NULL. There is no warning. */ + if ((ctx->scdf.ssa->var_info[ssa_op->op1_use].type & MAY_BE_ANY) == 0) { + op1 = &EG(uninitialized_zval); + } + break; + case ZEND_SEND_VAL: + case ZEND_SEND_VAR: + { + /* If the value of a SEND for an ICALL changes, we need to reconsider the + * ICALL result value. Otherwise we can ignore the opcode. */ + zend_call_info *call; + if (!ctx->call_map) { + return; + } + + call = ctx->call_map[opline - ctx->scdf.op_array->opcodes]; + if (IS_TOP(op1) || !call || call->caller_call_opline->opcode != ZEND_DO_ICALL) { + return; + } + + opline = call->caller_call_opline; + ssa_op = &ctx->scdf.ssa->ops[opline - ctx->scdf.op_array->opcodes]; + break; + } + } + + if ((op1 && IS_BOT(op1)) || (op2 && IS_BOT(op2))) { + /* If any operand is BOT, mark the result as BOT right away. + * Exceptions to this rule are handled above. */ + SET_RESULT_BOT(result); + SET_RESULT_BOT(op1); + SET_RESULT_BOT(op2); + return; + } + + switch (opline->opcode) { + case ZEND_ADD: + case ZEND_SUB: + case ZEND_MUL: + case ZEND_DIV: + case ZEND_MOD: + case ZEND_POW: + case ZEND_SL: + case ZEND_SR: + case ZEND_CONCAT: + case ZEND_FAST_CONCAT: + case ZEND_IS_EQUAL: + case ZEND_IS_NOT_EQUAL: + case ZEND_IS_SMALLER: + case ZEND_IS_SMALLER_OR_EQUAL: + case ZEND_IS_IDENTICAL: + case ZEND_IS_NOT_IDENTICAL: + case ZEND_BW_OR: + case ZEND_BW_AND: + case ZEND_BW_XOR: + case ZEND_BOOL_XOR: + case ZEND_CASE: + SKIP_IF_TOP(op1); + SKIP_IF_TOP(op2); + + if (zend_optimizer_eval_binary_op(&zv, opline->opcode, op1, op2) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_ASSIGN_ADD: + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + case ZEND_ASSIGN_CONCAT: + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + case ZEND_ASSIGN_POW: + /* Obj/dim compound assign */ + if (opline->extended_value) { + SET_RESULT_BOT(op1); + SET_RESULT_BOT(result); + break; + } + + SKIP_IF_TOP(op1); + SKIP_IF_TOP(op2); + + if (zend_optimizer_eval_binary_op(&zv, zend_compound_assign_to_binary_op(opline->opcode), op1, op2) == SUCCESS) { + SET_RESULT(op1, &zv); + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(op1); + SET_RESULT_BOT(result); + break; + case ZEND_PRE_INC: + case ZEND_PRE_DEC: + SKIP_IF_TOP(op1); + if (ct_eval_incdec(&zv, opline->opcode, op1) == SUCCESS) { + SET_RESULT(op1, &zv); + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(op1); + SET_RESULT_BOT(result); + break; + case ZEND_POST_INC: + case ZEND_POST_DEC: + SKIP_IF_TOP(op1); + SET_RESULT(result, op1); + if (ct_eval_incdec(&zv, opline->opcode, op1) == SUCCESS) { + SET_RESULT(op1, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(op1); + break; + case ZEND_BW_NOT: + case ZEND_BOOL_NOT: + SKIP_IF_TOP(op1); + if (zend_optimizer_eval_unary_op(&zv, opline->opcode, op1) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_CAST: + SKIP_IF_TOP(op1); + if (zend_optimizer_eval_cast(&zv, opline->extended_value, op1) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_BOOL: + case ZEND_JMPZ_EX: + case ZEND_JMPNZ_EX: + SKIP_IF_TOP(op1); + ZVAL_BOOL(&zv, zend_is_true(op1)); + SET_RESULT(result, &zv); + break; + case ZEND_STRLEN: + SKIP_IF_TOP(op1); + if (zend_optimizer_eval_strlen(&zv, op1) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_COUNT: + SKIP_IF_TOP(op1); + if (Z_TYPE_P(op1) == IS_ARRAY) { + ZVAL_LONG(&zv, zend_hash_num_elements(Z_ARRVAL_P(op1))); + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_FETCH_DIM_R: + case ZEND_FETCH_DIM_IS: + case ZEND_FETCH_LIST: + SKIP_IF_TOP(op1); + SKIP_IF_TOP(op2); + + if (ct_eval_fetch_dim(&zv, op1, op2, (opline->opcode != ZEND_FETCH_LIST)) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_ISSET_ISEMPTY_DIM_OBJ: + SKIP_IF_TOP(op1); + SKIP_IF_TOP(op2); + + if (ct_eval_isset_dim(&zv, opline->extended_value, op1, op2) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_QM_ASSIGN: + case ZEND_JMP_SET: + case ZEND_COALESCE: + SET_RESULT(result, op1); + break; + case ZEND_FETCH_CLASS: + if (!op1) { + SET_RESULT_BOT(result); + break; + } + SET_RESULT(result, op1); + break; + case ZEND_ISSET_ISEMPTY_VAR: + SKIP_IF_TOP(op1); + if (ct_eval_isset_isempty(&zv, opline->extended_value, op1) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_TYPE_CHECK: + SKIP_IF_TOP(op1); + ct_eval_type_check(&zv, opline->extended_value, op1); + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + case ZEND_INSTANCEOF: + SKIP_IF_TOP(op1); + ZVAL_FALSE(&zv); + SET_RESULT(result, &zv); + break; + case ZEND_ROPE_INIT: + SKIP_IF_TOP(op2); + if (zend_optimizer_eval_cast(&zv, IS_STRING, op2) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_ROPE_ADD: + case ZEND_ROPE_END: + // TODO The way this is currently implemented will result in quadratic runtime + // This is not necessary, the way the algorithm works it's okay to reuse the same + // string for all SSA vars with some extra checks + SKIP_IF_TOP(op1); + SKIP_IF_TOP(op2); + if (zend_optimizer_eval_binary_op(&zv, ZEND_CONCAT, op1, op2) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + break; + case ZEND_INIT_ARRAY: + case ZEND_ADD_ARRAY_ELEMENT: + { + zval *result = NULL; + if (opline->extended_value & ZEND_ARRAY_ELEMENT_REF) { + SET_RESULT_BOT(result); + SET_RESULT_BOT(op1); + break; + } + + if (opline->opcode == ZEND_ADD_ARRAY_ELEMENT) { + result = &ctx->values[ssa_op->result_use]; + if (IS_BOT(result)) { + SET_RESULT_BOT(result); + break; + } + SKIP_IF_TOP(result); + } + + SKIP_IF_TOP(op1); + if (op2) { + SKIP_IF_TOP(op2); + } + + /* We want to avoid keeping around intermediate arrays for each SSA variable in the + * ADD_ARRAY_ELEMENT chain. We do this by only keeping the array on the last opcode + * and use a NULL value everywhere else. */ + if (Z_TYPE(ctx->values[ssa_op->result_def]) == IS_NULL) { + break; + } + + if (result) { + ZVAL_COPY_VALUE(&zv, result); + ZVAL_NULL(result); + } else { + array_init(&zv); + } + + if (ct_eval_add_array_elem(&zv, op1, op2) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + zval_ptr_dtor_nogc(&zv); + break; + } + case ZEND_ASSIGN_DIM: + { + zval *data = get_op1_value(ctx, opline+1, ssa_op+1); + if (IS_BOT(data)) { + SET_RESULT_BOT(op1); + SET_RESULT_BOT(result); + break; + } + + SKIP_IF_TOP(data); + SKIP_IF_TOP(op1); + if (op2) { + SKIP_IF_TOP(op2); + } + + ZVAL_DUP(&zv, op1); + if (ct_eval_assign_dim(&zv, data, op2) == SUCCESS) { + SET_RESULT(result, data); + SET_RESULT(op1, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + SET_RESULT_BOT(result); + SET_RESULT_BOT(op1); + zval_ptr_dtor_nogc(&zv); + break; + } + case ZEND_DO_ICALL: + { + zend_call_info *call; + zval *name, *args[2] = {NULL}; + int i; + + if (!ctx->call_map) { + SET_RESULT_BOT(result); + break; + } + + call = ctx->call_map[opline - ctx->scdf.op_array->opcodes]; + name = CT_CONSTANT_EX(ctx->scdf.op_array, call->caller_init_opline->op2.constant); + + /* We already know it can't be evaluated, don't bother checking again */ + if (ssa_op->result_def < 0 || IS_BOT(&ctx->values[ssa_op->result_def])) { + break; + } + + /* We're only interested in functions with one, two or three arguments right now */ + if (call->num_args == 0 || call->num_args > 3) { + SET_RESULT_BOT(result); + break; + } + + for (i = 0; i < call->num_args; i++) { + zend_op *opline = call->arg_info[i].opline; + if (opline->opcode != ZEND_SEND_VAL && opline->opcode != ZEND_SEND_VAR) { + SET_RESULT_BOT(result); + return; + } + + args[i] = get_op1_value(ctx, opline, + &ctx->scdf.ssa->ops[opline - ctx->scdf.op_array->opcodes]); + if (args[i]) { + if (IS_BOT(args[i])) { + SET_RESULT_BOT(result); + return; + } else if (IS_TOP(args[i])) { + return; + } + } + } + + /* We didn't get a BOT argument, so value stays the same */ + if (!IS_TOP(&ctx->values[ssa_op->result_def])) { + break; + } + + if (ct_eval_func_call(&zv, Z_STR_P(name), call->num_args, args) == SUCCESS) { + SET_RESULT(result, &zv); + zval_ptr_dtor_nogc(&zv); + break; + } + +#if 0 + /* sort out | uniq -c | sort -n */ + fprintf(stderr, "%s\n", Z_STRVAL_P(name)); + /*if (args[1]) { + php_printf("%s %Z %Z\n", Z_STRVAL_P(name), args[0], args[1]); + } else { + php_printf("%s %Z\n", Z_STRVAL_P(name), args[0]); + }*/ +#endif + + SET_RESULT_BOT(result); + break; + } + default: + { + /* If we have no explicit implementation return BOT */ + SET_RESULT_BOT(result); + SET_RESULT_BOT(op1); + SET_RESULT_BOT(op2); + break; + } + } +} + +/* Returns whether there is a successor */ +static void sccp_mark_feasible_successors( + scdf_ctx *scdf, + int block_num, zend_basic_block *block, + zend_op *opline, zend_ssa_op *ssa_op) { + sccp_ctx *ctx = (sccp_ctx *) scdf; + zval *op1; + int s; + + /* We can't determine the branch target at compile-time for these */ + switch (opline->opcode) { + case ZEND_ASSERT_CHECK: + case ZEND_CATCH: + case ZEND_DECLARE_ANON_CLASS: + case ZEND_DECLARE_ANON_INHERITED_CLASS: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: + scdf_mark_edge_feasible(scdf, block_num, block->successors[0]); + scdf_mark_edge_feasible(scdf, block_num, block->successors[1]); + return; + } + + op1 = get_op1_value(ctx, opline, ssa_op); + + /* Branch target can be either one */ + if (!op1 || IS_BOT(op1)) { + for (s = 0; s < block->successors_count; s++) { + scdf_mark_edge_feasible(scdf, block_num, block->successors[s]); + } + return; + } + + /* Branch target not yet known */ + if (IS_TOP(op1)) { + return; + } + + switch (opline->opcode) { + case ZEND_JMPZ: + case ZEND_JMPZNZ: + case ZEND_JMPZ_EX: + s = zend_is_true(op1); + break; + case ZEND_JMPNZ: + case ZEND_JMPNZ_EX: + case ZEND_JMP_SET: + s = !zend_is_true(op1); + break; + case ZEND_COALESCE: + s = (Z_TYPE_P(op1) == IS_NULL); + break; + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: + if (Z_TYPE_P(op1) != IS_ARRAY) { + scdf_mark_edge_feasible(scdf, block_num, block->successors[0]); + scdf_mark_edge_feasible(scdf, block_num, block->successors[1]); + return; + } + s = zend_hash_num_elements(Z_ARR_P(op1)) != 0; + break; + default: + for (s = 0; s < block->successors_count; s++) { + scdf_mark_edge_feasible(scdf, block_num, block->successors[s]); + } + return; + } + scdf_mark_edge_feasible(scdf, block_num, block->successors[s]); +} + +static void join_phi_values(zval *a, zval *b) { + if (IS_BOT(a) || IS_TOP(b)) { + return; + } + if (IS_TOP(a)) { + zval_ptr_dtor_nogc(a); + ZVAL_COPY(a, b); + return; + } + if (IS_BOT(b) || !zend_is_identical(a, b)) { + zval_ptr_dtor_nogc(a); + MAKE_BOT(a); + } +} + +static void sccp_visit_phi(scdf_ctx *scdf, zend_ssa_phi *phi) { + sccp_ctx *ctx = (sccp_ctx *) scdf; + zend_ssa *ssa = scdf->ssa; + ZEND_ASSERT(phi->ssa_var >= 0); + if (!IS_BOT(&ctx->values[phi->ssa_var])) { + zend_basic_block *block = &ssa->cfg.blocks[phi->block]; + int *predecessors = &ssa->cfg.predecessors[block->predecessor_offset]; + + int i; + zval result; + MAKE_TOP(&result); + SCP_DEBUG("Handling PHI("); + if (phi->pi >= 0) { + ZEND_ASSERT(phi->sources[0] >= 0); + if (scdf_is_edge_feasible(scdf, phi->pi, phi->block)) { + join_phi_values(&result, &ctx->values[phi->sources[0]]); + } + } else { + for (i = 0; i < block->predecessors_count; i++) { + ZEND_ASSERT(phi->sources[i] >= 0); + if (scdf_is_edge_feasible(scdf, predecessors[i], phi->block)) { + SCP_DEBUG("val, "); + join_phi_values(&result, &ctx->values[phi->sources[i]]); + } else { + SCP_DEBUG("--, "); + } + } + } + SCP_DEBUG(")\n"); + + set_value(scdf, ctx, phi->ssa_var, &result); + zval_ptr_dtor_nogc(&result); + } +} + +static zval *value_from_type_and_range(sccp_ctx *ctx, int var_num, zval *tmp) { + zend_ssa *ssa = ctx->scdf.ssa; + zend_ssa_var_info *info = &ssa->var_info[var_num]; + + if (ssa->vars[var_num].var >= ctx->scdf.op_array->last_var) { + // TODO Non-CVs may cause issues with FREEs + return NULL; + } + + if (info->type & MAY_BE_UNDEF) { + return NULL; + } + + if (!(info->type & ((MAY_BE_ANY|MAY_BE_UNDEF)-MAY_BE_NULL))) { + ZVAL_NULL(tmp); + return tmp; + } + if (!(info->type & ((MAY_BE_ANY|MAY_BE_UNDEF)-MAY_BE_FALSE))) { + ZVAL_FALSE(tmp); + return tmp; + } + if (!(info->type & ((MAY_BE_ANY|MAY_BE_UNDEF)-MAY_BE_TRUE))) { + ZVAL_TRUE(tmp); + return tmp; + } + + if (!(info->type & ((MAY_BE_ANY|MAY_BE_UNDEF)-MAY_BE_LONG)) + && info->has_range + && !info->range.overflow && !info->range.underflow + && info->range.min == info->range.max) { + ZVAL_LONG(tmp, info->range.min); + return tmp; + } + + return NULL; +} + +/* This will try to replace uses of SSA variables we have determined to be constant. Not all uses + * can be replaced, because some instructions don't accept constant operands or only accept them + * if they have a certain type. */ +static int replace_constant_operands(sccp_ctx *ctx) { + zend_ssa *ssa = ctx->scdf.ssa; + zend_op_array *op_array = ctx->scdf.op_array; + int i; + zval tmp; + int removed_ops = 0; + + /* We iterate the variables backwards, so we can eliminate sequences like INIT_ROPE + * and INIT_ARRAY. */ + for (i = ssa->vars_count - 1; i >= op_array->last_var; i--) { + zend_ssa_var *var = &ssa->vars[i]; + zval *value; + int use; + + if (value_known(&ctx->values[i])) { + value = &ctx->values[i]; + } else { + value = value_from_type_and_range(ctx, i, &tmp); + if (!value) { + continue; + } + } + + FOREACH_USE(var, use) { + zend_op *opline = &op_array->opcodes[use]; + zend_ssa_op *ssa_op = &ssa->ops[use]; + if (try_replace_op1(ctx, opline, ssa_op, i, value)) { + if (opline->opcode == ZEND_NOP) { + removed_ops++; + } + ZEND_ASSERT(ssa_op->op1_def == -1); + if (ssa_op->op1_use != ssa_op->op2_use) { + zend_ssa_unlink_use_chain(ssa, use, ssa_op->op1_use); + } else { + ssa_op->op2_use_chain = ssa_op->op1_use_chain; + } + ssa_op->op1_use = -1; + ssa_op->op1_use_chain = -1; + } + if (try_replace_op2(ctx, opline, ssa_op, i, value)) { + ZEND_ASSERT(ssa_op->op2_def == -1); + zend_ssa_unlink_use_chain(ssa, use, ssa_op->op2_use); + ssa_op->op2_use = -1; + ssa_op->op2_use_chain = -1; + } + } FOREACH_USE_END(); + + /* This is a basic DCE pass we run after SCCP. It only works on those instructions those result + * value(s) were determined by SCCP. It removes dead computational instructions and converts + * CV-affecting instructions into CONST ASSIGNs. This basic DCE is performed for multiple reasons: + * a) During operand replacement we eliminate FREEs. The corresponding computational instructions + * must be removed to avoid leaks. This way SCCP can run independently of the full DCE pass. + * b) The main DCE pass relies on type analysis to determine whether instructions have side-effects + * and can't be DCEd. This means that it will not be able collect all instructions rendered dead + * by SCCP, because they may have potentially side-effecting types, but the actual values are + * not. As such doing DCE here will allow us to eliminate more dead code in combination. + * c) The ordinary DCE pass cannot collect dead calls. However SCCP can result in dead calls, which + * we need to collect. */ + + if (var->definition >= 0 && value_known(&ctx->values[i])) { + zend_op *opline = &op_array->opcodes[var->definition]; + zend_ssa_op *ssa_op = &ssa->ops[var->definition]; + if (opline->opcode == ZEND_ASSIGN) { + /* Leave assigns to DCE (due to dtor effects) */ + continue; + } + + if (ssa_op->result_def == i + && ssa_op->op1_def < 0 + && ssa_op->op2_def < 0 + && var->use_chain < 0 + && var->phi_use_chain == NULL) { + if (opline->opcode == ZEND_DO_ICALL) { + /* Call instruction -> remove opcodes that are part of the call */ + zend_call_info *call; + int i; + + ZEND_ASSERT(ctx->call_map); + call = ctx->call_map[var->definition]; + ZEND_ASSERT(call); + ZEND_ASSERT(call->caller_call_opline == opline); + if (opline->result_type & (IS_TMP_VAR|IS_VAR)) { + zend_optimizer_remove_live_range_ex(op_array, opline->result.var, var->definition + 1); + } + zend_ssa_remove_result_def(ssa, ssa_op); + zend_ssa_remove_instr(ssa, opline, ssa_op); + zend_ssa_remove_instr(ssa, call->caller_init_opline, + &ssa->ops[call->caller_init_opline - op_array->opcodes]); + + for (i = 0; i < call->num_args; i++) { + zend_ssa_remove_instr(ssa, call->arg_info[i].opline, + &ssa->ops[call->arg_info[i].opline - op_array->opcodes]); + } + removed_ops = call->num_args + 2; + + // TODO: remove call_info completely??? + call->callee_func = NULL; + } else { + /* Ordinary computational instruction -> remove it */ + if (opline->result_type & (IS_TMP_VAR|IS_VAR)) { + zend_optimizer_remove_live_range_ex(op_array, opline->result.var, var->definition + 1); + } + zend_ssa_remove_result_def(ssa, ssa_op); + zend_ssa_remove_instr(ssa, opline, ssa_op); + removed_ops++; + } + } else if (ssa_op->op1_def == i) { + /* Compound assign or incdec -> convert to direct ASSIGN */ + + /* Destroy previous op2 */ + if (opline->op2_type == IS_CONST) { + literal_dtor(&ZEND_OP2_LITERAL(opline)); + } else if (ssa_op->op2_use >= 0) { + if (ssa_op->op2_use != ssa_op->op1_use) { + zend_ssa_unlink_use_chain(ssa, var->definition, ssa_op->op2_use); + } + ssa_op->op2_use = -1; + ssa_op->op2_use_chain = -1; + } + + /* Mark result unused, if possible */ + if (ssa_op->result_def >= 0 + && ssa->vars[ssa_op->result_def].use_chain < 0 + && ssa->vars[ssa_op->result_def].phi_use_chain == NULL) { + if (opline->result_type & (IS_TMP_VAR|IS_VAR)) { + zend_optimizer_remove_live_range_ex(op_array, opline->result.var, var->definition + 1); + } + zend_ssa_remove_result_def(ssa, ssa_op); + opline->result_type = IS_UNUSED; + } + + /* Remove OP_DATA opcode */ + if (opline->opcode == ZEND_ASSIGN_DIM) { + removed_ops++; + zend_ssa_remove_instr(ssa, opline + 1, ssa_op + 1); + } + + /* Convert to ASSIGN */ + opline->opcode = ZEND_ASSIGN; + opline->op2_type = IS_CONST; + opline->op2.constant = zend_optimizer_add_literal(op_array, value); + Z_TRY_ADDREF_P(value); + } + } + if (var->definition_phi + && value_known(&ctx->values[i]) + && var->use_chain < 0 + && var->phi_use_chain == NULL) { + zend_ssa_remove_phi(ssa, var->definition_phi); + } + } + + return removed_ops; +} + +static void sccp_context_init(zend_optimizer_ctx *ctx, sccp_ctx *sccp, + zend_ssa *ssa, zend_op_array *op_array, zend_call_info **call_map) { + int i; + sccp->call_map = call_map; + sccp->values = zend_arena_alloc(&ctx->arena, sizeof(zval) * ssa->vars_count); + + MAKE_TOP(&sccp->top); + MAKE_BOT(&sccp->bot); + + i = 0; + for (; i < op_array->last_var; ++i) { + /* These are all undefined variables, which we have to mark BOT. + * Otherwise the undefined variable warning might not be preserved. */ + MAKE_BOT(&sccp->values[i]); + } + for (; i < ssa->vars_count; ++i) { + if (ssa->vars[i].alias) { + MAKE_BOT(&sccp->values[i]); + } else { + MAKE_TOP(&sccp->values[i]); + } + } +} + +static void sccp_context_free(sccp_ctx *sccp) { + int i; + for (i = sccp->scdf.op_array->last_var; i < sccp->scdf.ssa->vars_count; ++i) { + zval_ptr_dtor_nogc(&sccp->values[i]); + } +} + +int sccp_optimize_op_array(zend_optimizer_ctx *ctx, zend_op_array *op_array, zend_ssa *ssa, zend_call_info **call_map) +{ + sccp_ctx sccp; + int removed_ops = 0; + void *checkpoint = zend_arena_checkpoint(ctx->arena); + + sccp_context_init(ctx, &sccp, ssa, op_array, call_map); + + sccp.scdf.handlers.visit_instr = sccp_visit_instr; + sccp.scdf.handlers.visit_phi = sccp_visit_phi; + sccp.scdf.handlers.mark_feasible_successors = sccp_mark_feasible_successors; + + scdf_init(ctx, &sccp.scdf, op_array, ssa); + scdf_solve(&sccp.scdf, "SCCP"); + + removed_ops += scdf_remove_unreachable_blocks(&sccp.scdf); + removed_ops += replace_constant_operands(&sccp); + + sccp_context_free(&sccp); + zend_arena_release(&ctx->arena, checkpoint); + + return removed_ops; +} diff --git a/ext/opcache/Optimizer/scdf.c b/ext/opcache/Optimizer/scdf.c new file mode 100644 index 0000000000..add8741af6 --- /dev/null +++ b/ext/opcache/Optimizer/scdf.c @@ -0,0 +1,228 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, Sparse Conditional Data Flow Propagation Framework | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Nikita Popov | + +----------------------------------------------------------------------+ +*/ + +#include "ZendAccelerator.h" +#include "Optimizer/zend_optimizer_internal.h" +#include "Optimizer/scdf.h" + +/* This defines a generic framework for sparse conditional dataflow propagation. The algorithm is + * based on "Sparse conditional constant propagation" by Wegman and Zadeck. We're using a + * generalized implementation as described in chapter 8.3 of the SSA book. + * + * Every SSA variable is associated with an element on a finite-height lattice, those value can only + * ever be lowered during the operation of the algorithm. If a value is lowered all instructions and + * phis using that value need to be reconsidered (this is done by adding the variable to a + * worklist). For phi functions the result is computed by applying the meet operation to the + * operands. This continues until a fixed point is reached. + * + * The algorithm is control-flow sensitive: All blocks except the start block are initially assumed + * to be unreachable. When considering a branch instruction, we determine the feasible successors + * based on the current state of the variable lattice. If a new edge becomes feasible we either have + * to mark the successor block executable and consider all instructions in it, or, if the target is + * already executable, we only have to reconsider the phi functions (as we only consider phi + * operands which are associated with a feasible edge). + * + * The generic framework requires the definition of three functions: + * * visit_instr() should recompute the lattice values of all SSA variables defined by an + * instruction. + * * visit_phi() should recompute the lattice value of the SSA variable defined by the phi. While + * doing this it should only consider operands for which scfg_is_edge_feasible() returns true. + * * get_feasible_successors() should determine the feasible successors for a branch instruction. + * Note that this callback only needs to handle conditional branches (with two successors). + */ + +#if 0 +#define DEBUG_PRINT(...) fprintf(stderr, __VA_ARGS__) +#else +#define DEBUG_PRINT(...) +#endif + +void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to) { + uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to); + + if (zend_bitset_in(scdf->feasible_edges, edge)) { + /* We already handled this edge */ + return; + } + + DEBUG_PRINT("Marking edge %d->%d feasible\n", from, to); + zend_bitset_incl(scdf->feasible_edges, edge); + + if (!zend_bitset_in(scdf->executable_blocks, to)) { + if (!zend_bitset_in(scdf->block_worklist, to)) { + DEBUG_PRINT("Adding block %d to worklist\n", to); + } + zend_bitset_incl(scdf->block_worklist, to); + } else { + /* Block is already executable, only a new edge became feasible. + * Reevaluate phi nodes to account for changed source operands. */ + zend_ssa_block *ssa_block = &scdf->ssa->blocks[to]; + zend_ssa_phi *phi; + for (phi = ssa_block->phis; phi; phi = phi->next) { + zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var); + scdf->handlers.visit_phi(scdf, phi); + } + } +} + +void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa) { + uint32_t edges_count = 0; + int b; + + for (b = 0; b < ssa->cfg.blocks_count; b++) { + edges_count += ssa->cfg.blocks[b].predecessors_count; + } + + scdf->op_array = op_array; + scdf->ssa = ssa; + + scdf->instr_worklist_len = zend_bitset_len(op_array->last); + scdf->phi_var_worklist_len = zend_bitset_len(ssa->vars_count); + scdf->block_worklist_len = zend_bitset_len(ssa->cfg.blocks_count); + + scdf->instr_worklist = zend_arena_calloc(&ctx->arena, + scdf->instr_worklist_len + scdf->phi_var_worklist_len + 2 * scdf->block_worklist_len + zend_bitset_len(edges_count), + sizeof(zend_ulong)); + + scdf->phi_var_worklist = scdf->instr_worklist + scdf->instr_worklist_len; + scdf->block_worklist = scdf->phi_var_worklist + scdf->phi_var_worklist_len; + scdf->executable_blocks = scdf->block_worklist + scdf->block_worklist_len; + scdf->feasible_edges = scdf->executable_blocks + scdf->block_worklist_len; + + zend_bitset_incl(scdf->block_worklist, 0); + zend_bitset_incl(scdf->executable_blocks, 0); +} + +void scdf_solve(scdf_ctx *scdf, const char *name) { + zend_ssa *ssa = scdf->ssa; + DEBUG_PRINT("Start SCDF solve (%s)\n", name); + while (!zend_bitset_empty(scdf->instr_worklist, scdf->instr_worklist_len) + || !zend_bitset_empty(scdf->phi_var_worklist, scdf->phi_var_worklist_len) + || !zend_bitset_empty(scdf->block_worklist, scdf->block_worklist_len) + ) { + int i; + while ((i = zend_bitset_pop_first(scdf->phi_var_worklist, scdf->phi_var_worklist_len)) >= 0) { + zend_ssa_phi *phi = ssa->vars[i].definition_phi; + ZEND_ASSERT(phi); + if (zend_bitset_in(scdf->executable_blocks, phi->block)) { + scdf->handlers.visit_phi(scdf, phi); + } + } + + while ((i = zend_bitset_pop_first(scdf->instr_worklist, scdf->instr_worklist_len)) >= 0) { + int block_num = ssa->cfg.map[i]; + if (zend_bitset_in(scdf->executable_blocks, block_num)) { + zend_basic_block *block = &ssa->cfg.blocks[block_num]; + zend_op *opline = &scdf->op_array->opcodes[i]; + zend_ssa_op *ssa_op = &ssa->ops[i]; + if (opline->opcode == ZEND_OP_DATA) { + opline--; + ssa_op--; + } + scdf->handlers.visit_instr(scdf, opline, ssa_op); + if (i == block->start + block->len - 1) { + if (block->successors_count == 1) { + scdf_mark_edge_feasible(scdf, block_num, block->successors[0]); + } else if (block->successors_count > 1) { + scdf->handlers.mark_feasible_successors(scdf, block_num, block, opline, ssa_op); + } + } + } + } + + while ((i = zend_bitset_pop_first(scdf->block_worklist, scdf->block_worklist_len)) >= 0) { + /* This block is now live. Interpret phis and instructions in it. */ + zend_basic_block *block = &ssa->cfg.blocks[i]; + zend_ssa_block *ssa_block = &ssa->blocks[i]; + + DEBUG_PRINT("Pop block %d from worklist\n", i); + zend_bitset_incl(scdf->executable_blocks, i); + + { + zend_ssa_phi *phi; + for (phi = ssa_block->phis; phi; phi = phi->next) { + zend_bitset_excl(scdf->phi_var_worklist, phi->ssa_var); + scdf->handlers.visit_phi(scdf, phi); + } + } + + if (block->len == 0) { + /* Zero length blocks don't have a last instruction that would normally do this */ + scdf_mark_edge_feasible(scdf, i, block->successors[0]); + } else { + zend_op *opline; + int j, end = block->start + block->len; + for (j = block->start; j < end; j++) { + opline = &scdf->op_array->opcodes[j]; + zend_bitset_excl(scdf->instr_worklist, j); + if (opline->opcode != ZEND_OP_DATA) { + scdf->handlers.visit_instr(scdf, opline, &ssa->ops[j]); + } + } + if (block->successors_count == 1) { + scdf_mark_edge_feasible(scdf, i, block->successors[0]); + } else if (block->successors_count > 1) { + if (opline->opcode == ZEND_OP_DATA) { + opline--; + j--; + } + scdf->handlers.mark_feasible_successors(scdf, i, block, opline, &ssa->ops[j-1]); + } + } + } + } +} + +/* If a live range starts in a reachable block and ends in an unreachable block, we should + * not eliminate the latter. While it cannot be reached, the FREE opcode of the loop var + * is necessary for the correctness of temporary compaction. */ +static zend_bool kept_alive_by_live_range(scdf_ctx *scdf, uint32_t block) { + uint32_t i; + const zend_op_array *op_array = scdf->op_array; + const zend_cfg *cfg = &scdf->ssa->cfg; + for (i = 0; i < op_array->last_live_range; i++) { + zend_live_range *live_range = &op_array->live_range[i]; + uint32_t start_block = cfg->map[live_range->start]; + uint32_t end_block = cfg->map[live_range->end]; + + if (end_block == block && start_block != block + && zend_bitset_in(scdf->executable_blocks, start_block)) { + return 1; + } + } + return 0; +} + +/* Removes unreachable blocks. This will remove both the instructions (and phis) in the + * blocks, as well as remove them from the successor / predecessor lists and mark them + * unreachable. Blocks already marked unreachable are not removed. */ +int scdf_remove_unreachable_blocks(scdf_ctx *scdf) { + zend_ssa *ssa = scdf->ssa; + int i; + int removed_ops = 0; + + for (i = 0; i < ssa->cfg.blocks_count; i++) { + if (!zend_bitset_in(scdf->executable_blocks, i) + && (ssa->cfg.blocks[i].flags & ZEND_BB_REACHABLE) + && !kept_alive_by_live_range(scdf, i)) { + removed_ops += ssa->cfg.blocks[i].len; + zend_ssa_remove_block(scdf->op_array, ssa, i); + } + } + return removed_ops; +} diff --git a/ext/opcache/Optimizer/scdf.h b/ext/opcache/Optimizer/scdf.h new file mode 100644 index 0000000000..6291534286 --- /dev/null +++ b/ext/opcache/Optimizer/scdf.h @@ -0,0 +1,99 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, Call Graph | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Nikita Popov | + +----------------------------------------------------------------------+ +*/ + +#ifndef _SCDF_H +#define _SCDF_H + +#include "zend_bitset.h" + +typedef struct _scdf_ctx { + zend_op_array *op_array; + zend_ssa *ssa; + zend_bitset instr_worklist; + /* Represent phi-instructions through the defining var */ + zend_bitset phi_var_worklist; + zend_bitset block_worklist; + zend_bitset executable_blocks; + /* 1 bit per edge, see scdf_edge(cfg, from, to) */ + zend_bitset feasible_edges; + uint32_t instr_worklist_len; + uint32_t phi_var_worklist_len; + uint32_t block_worklist_len; + + struct { + void (*visit_instr)( + struct _scdf_ctx *scdf, zend_op *opline, zend_ssa_op *ssa_op); + void (*visit_phi)( + struct _scdf_ctx *scdf, zend_ssa_phi *phi); + void (*mark_feasible_successors)( + struct _scdf_ctx *scdf, int block_num, zend_basic_block *block, + zend_op *opline, zend_ssa_op *ssa_op); + } handlers; +} scdf_ctx; + +void scdf_init(zend_optimizer_ctx *ctx, scdf_ctx *scdf, zend_op_array *op_array, zend_ssa *ssa); +void scdf_solve(scdf_ctx *scdf, const char *name); + +int scdf_remove_unreachable_blocks(scdf_ctx *scdf); + +/* Add uses to worklist */ +static inline void scdf_add_to_worklist(scdf_ctx *scdf, int var_num) { + zend_ssa *ssa = scdf->ssa; + zend_ssa_var *var = &ssa->vars[var_num]; + int use; + zend_ssa_phi *phi; + FOREACH_USE(var, use) { + zend_bitset_incl(scdf->instr_worklist, use); + } FOREACH_USE_END(); + FOREACH_PHI_USE(var, phi) { + zend_bitset_incl(scdf->phi_var_worklist, phi->ssa_var); + } FOREACH_PHI_USE_END(); +} + +/* This should usually not be necessary, however it's used for type narrowing. */ +static inline void scdf_add_def_to_worklist(scdf_ctx *scdf, int var_num) { + zend_ssa_var *var = &scdf->ssa->vars[var_num]; + if (var->definition >= 0) { + zend_bitset_incl(scdf->instr_worklist, var->definition); + } else if (var->definition_phi) { + zend_bitset_incl(scdf->phi_var_worklist, var_num); + } +} + +static inline uint32_t scdf_edge(zend_cfg *cfg, int from, int to) { + zend_basic_block *to_block = cfg->blocks + to; + int i; + + for (i = 0; i < to_block->predecessors_count; i++) { + uint32_t edge = to_block->predecessor_offset + i; + + if (cfg->predecessors[edge] == from) { + return edge; + } + } + ZEND_ASSERT(0); +} + +static inline zend_bool scdf_is_edge_feasible(scdf_ctx *scdf, int from, int to) { + uint32_t edge = scdf_edge(&scdf->ssa->cfg, from, to); + return zend_bitset_in(scdf->feasible_edges, edge); +} + +void scdf_mark_edge_feasible(scdf_ctx *scdf, int from, int to); + +#endif diff --git a/ext/opcache/Optimizer/ssa_integrity.c b/ext/opcache/Optimizer/ssa_integrity.c new file mode 100644 index 0000000000..ae3495b903 --- /dev/null +++ b/ext/opcache/Optimizer/ssa_integrity.c @@ -0,0 +1,369 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine, SSA validation | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2017 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Nikita Popov | + +----------------------------------------------------------------------+ +*/ + +#include "ZendAccelerator.h" +#include "Optimizer/zend_optimizer_internal.h" + +/* The ssa_verify_integrity() function ensures that that certain invariants of the SSA form and + * CFG are upheld and prints messages to stderr if this is not the case. */ + +static inline zend_bool is_in_use_chain(zend_ssa *ssa, int var, int check) { + int use; + FOREACH_USE(&ssa->vars[var], use) { + if (use == check) { + return 1; + } + } FOREACH_USE_END(); + return 0; +} + +static inline zend_bool is_in_phi_use_chain(zend_ssa *ssa, int var, zend_ssa_phi *check) { + zend_ssa_phi *phi; + FOREACH_PHI_USE(&ssa->vars[var], phi) { + if (phi == check) { + return 1; + } + } FOREACH_PHI_USE_END(); + return 0; +} + +static inline zend_bool is_used_by_op(zend_ssa *ssa, int op, int check) { + zend_ssa_op *ssa_op = &ssa->ops[op]; + return (ssa_op->op1_use == check) + || (ssa_op->op2_use == check) + || (ssa_op->result_use == check); +} + +static inline zend_bool is_defined_by_op(zend_ssa *ssa, int op, int check) { + zend_ssa_op *ssa_op = &ssa->ops[op]; + return (ssa_op->op1_def == check) + || (ssa_op->op2_def == check) + || (ssa_op->result_def == check); +} + +static inline zend_bool is_in_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi, int check) { + int source; + FOREACH_PHI_SOURCE(phi, source) { + if (source == check) { + return 1; + } + } FOREACH_PHI_SOURCE_END(); + return 0; +} + +static inline zend_bool is_in_predecessors(zend_cfg *cfg, zend_basic_block *block, int check) { + int i, *predecessors = &cfg->predecessors[block->predecessor_offset]; + for (i = 0; i < block->predecessors_count; i++) { + if (predecessors[i] == check) { + return 1; + } + } + return 0; +} + +static inline zend_bool is_in_successors(zend_basic_block *block, int check) { + int s; + for (s = 0; s < block->successors_count; s++) { + if (block->successors[s] == check) { + return 1; + } + } + return 0; +} + +static inline zend_bool is_var_type(zend_uchar type) { + return type == IS_CV || type == IS_VAR || type == IS_TMP_VAR; +} + +#define FAIL(...) do { \ + if (status == SUCCESS) { \ + fprintf(stderr, "\nIn function %s::%s (%s):\n", \ + op_array->scope ? ZSTR_VAL(op_array->scope->name) : "", \ + op_array->function_name ? ZSTR_VAL(op_array->function_name) : "{main}", extra); \ + } \ + fprintf(stderr, __VA_ARGS__); \ + status = FAILURE; \ +} while (0) + +#define VARFMT "%d (%s%s)" +#define VAR(i) \ + (i), (ssa->vars[i].var < op_array->last_var ? "CV $" : "TMP"), \ + (ssa->vars[i].var < op_array->last_var ? ZSTR_VAL(op_array->vars[ssa->vars[i].var]) : "") + +#define INSTRFMT "%d (%s)" +#define INSTR(i) \ + (i), (zend_get_opcode_name(op_array->opcodes[i].opcode)) + +int ssa_verify_integrity(zend_op_array *op_array, zend_ssa *ssa, const char *extra) { + zend_cfg *cfg = &ssa->cfg; + zend_ssa_phi *phi; + int i, status = SUCCESS; + + /* Vars */ + for (i = 0; i < ssa->vars_count; i++) { + zend_ssa_var *var = &ssa->vars[i]; + int use, c; + uint32_t type = ssa->var_info[i].type; + + if (var->definition < 0 && !var->definition_phi && i > op_array->last_var) { + if (var->use_chain >= 0) { + FAIL("var " VARFMT " without def has op uses\n", VAR(i)); + } + if (var->phi_use_chain) { + FAIL("var " VARFMT " without def has phi uses\n", VAR(i)); + } + } + if (var->definition >= 0 && var->definition_phi) { + FAIL("var " VARFMT " has both def and def_phi\n", VAR(i)); + } + if (var->definition >= 0) { + if (!is_defined_by_op(ssa, var->definition, i)) { + FAIL("var " VARFMT " not defined by op " INSTRFMT "\n", + VAR(i), INSTR(var->definition)); + } + } + if (var->definition_phi) { + if (var->definition_phi->ssa_var != i) { + FAIL("var " VARFMT " not defined by given phi\n", VAR(i)); + } + } + + c = 0; + FOREACH_USE(var, use) { + if (++c > 10000) { + FAIL("cycle in uses of " VARFMT "\n", VAR(i)); + return status; + } + if (!is_used_by_op(ssa, use, i)) { + fprintf(stderr, "var " VARFMT " not in uses of op %d\n", VAR(i), use); + } + } FOREACH_USE_END(); + + c = 0; + FOREACH_PHI_USE(var, phi) { + if (++c > 10000) { + FAIL("cycle in phi uses of " VARFMT "\n", VAR(i)); + return status; + } + if (!is_in_phi_sources(ssa, phi, i)) { + FAIL("var " VARFMT " not in phi sources of %d\n", VAR(i), phi->ssa_var); + } + } FOREACH_PHI_USE_END(); + + if ((type & MAY_BE_ARRAY_KEY_ANY) && !(type & MAY_BE_ARRAY_OF_ANY)) { + FAIL("var " VARFMT " has array key type but not value type\n", VAR(i)); + } + if ((type & MAY_BE_ARRAY_OF_ANY) && !(type & MAY_BE_ARRAY_KEY_ANY)) { + FAIL("var " VARFMT " has array value type but not key type\n", VAR(i)); + } + } + + /* Instructions */ + FOREACH_INSTR_NUM(i) { + zend_ssa_op *ssa_op = &ssa->ops[i]; + zend_op *opline = &op_array->opcodes[i]; + if (is_var_type(opline->op1_type)) { + if (ssa_op->op1_use < 0 && ssa_op->op1_def < 0) { + FAIL("var op1 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i)); + } + } else { + if (ssa_op->op1_use >= 0 || ssa_op->op1_def >= 0) { + FAIL("non-var op1 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i)); + } + } + if (is_var_type(opline->op2_type)) { + if (ssa_op->op2_use < 0 && ssa_op->op2_def < 0) { + FAIL("var op2 of " INSTRFMT " does not use/def an ssa var\n", INSTR(i)); + } + } else { + if (ssa_op->op2_use >= 0 || ssa_op->op2_def >= 0) { + FAIL("non-var op2 of " INSTRFMT " uses or defs an ssa var\n", INSTR(i)); + } + } + if (is_var_type(opline->result_type)) { + if (ssa_op->result_use < 0 && ssa_op->result_def < 0) { + FAIL("var result of " INSTRFMT " does not use/def an ssa var\n", INSTR(i)); + } + } else { + if (ssa_op->result_use >= 0 || ssa_op->result_def >= 0) { + FAIL("non-var result of " INSTRFMT " uses or defs an ssa var\n", INSTR(i)); + } + } + + if (ssa_op->op1_use >= 0) { + if (ssa_op->op1_use >= ssa->vars_count) { + FAIL("op1 use %d out of range\n", ssa_op->op1_use); + } + if (!is_in_use_chain(ssa, ssa_op->op1_use, i)) { + FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n", + VAR(ssa_op->op1_use), INSTR(i)); + } + if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_use].var) { + FAIL("op1 use of " VARFMT " does not match op %d of " INSTRFMT "\n", + VAR(ssa_op->op1_use), VAR_NUM(opline->op1.var), INSTR(i)); + } + } + if (ssa_op->op2_use >= 0) { + if (ssa_op->op2_use >= ssa->vars_count) { + FAIL("op2 use %d out of range\n", ssa_op->op2_use); + } + if (!is_in_use_chain(ssa, ssa_op->op2_use, i)) { + FAIL("op1 use of " VARFMT " in " INSTRFMT " not in use chain\n", + VAR(ssa_op->op2_use), INSTR(i)); + } + if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_use].var) { + FAIL("op2 use of " VARFMT " does not match op %d of " INSTRFMT "\n", + VAR(ssa_op->op2_use), VAR_NUM(opline->op2.var), INSTR(i)); + } + } + if (ssa_op->result_use >= 0) { + if (ssa_op->result_use >= ssa->vars_count) { + FAIL("result use %d out of range\n", ssa_op->result_use); + } + if (!is_in_use_chain(ssa, ssa_op->result_use, i)) { + FAIL("result use of " VARFMT " in " INSTRFMT " not in use chain\n", + VAR(ssa_op->result_use), INSTR(i)); + } + if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_use].var) { + FAIL("result use of " VARFMT " does not match op %d of " INSTRFMT "\n", + VAR(ssa_op->result_use), VAR_NUM(opline->result.var), INSTR(i)); + } + } + if (ssa_op->op1_def >= 0) { + if (ssa_op->op1_def >= ssa->vars_count) { + FAIL("op1 def %d out of range\n", ssa_op->op1_def); + } + if (ssa->vars[ssa_op->op1_def].definition != i) { + FAIL("op1 def of " VARFMT " in " INSTRFMT " invalid\n", + VAR(ssa_op->op1_def), INSTR(i)); + } + if (VAR_NUM(opline->op1.var) != ssa->vars[ssa_op->op1_def].var) { + FAIL("op1 def of " VARFMT " does not match op %d of " INSTRFMT "\n", + VAR(ssa_op->op1_def), VAR_NUM(opline->op1.var), INSTR(i)); + } + } + if (ssa_op->op2_def >= 0) { + if (ssa_op->op2_def >= ssa->vars_count) { + FAIL("op2 def %d out of range\n", ssa_op->op2_def); + } + if (ssa->vars[ssa_op->op2_def].definition != i) { + FAIL("op2 def of " VARFMT " in " INSTRFMT " invalid\n", + VAR(ssa_op->op2_def), INSTR(i)); + } + if (VAR_NUM(opline->op2.var) != ssa->vars[ssa_op->op2_def].var) { + FAIL("op2 def of " VARFMT " does not match op %d of " INSTRFMT "\n", + VAR(ssa_op->op2_def), VAR_NUM(opline->op2.var), INSTR(i)); + } + } + if (ssa_op->result_def >= 0) { + if (ssa_op->result_def >= ssa->vars_count) { + FAIL("result def %d out of range\n", ssa_op->result_def); + } + if (ssa->vars[ssa_op->result_def].definition != i) { + FAIL("result def of " VARFMT " in " INSTRFMT " invalid\n", + VAR(ssa_op->result_def), INSTR(i)); + } + if (VAR_NUM(opline->result.var) != ssa->vars[ssa_op->result_def].var) { + FAIL("result def of " VARFMT " does not match op %d of " INSTRFMT "\n", + VAR(ssa_op->result_def), VAR_NUM(opline->result.var), INSTR(i)); + } + } + } FOREACH_INSTR_NUM_END(); + + /* Phis */ + FOREACH_PHI(phi) { + int source; + FOREACH_PHI_SOURCE(phi, source) { + if (source < 0) { + FAIL(VARFMT " negative source\n", VAR(phi->ssa_var)); + } + if (!is_in_phi_use_chain(ssa, source, phi)) { + FAIL(VARFMT " not in phi use chain of %d\n", VAR(phi->ssa_var), source); + } + if (ssa->vars[source].var != ssa->vars[phi->ssa_var].var) { + FAIL(VARFMT " source of phi for " VARFMT "\n", VAR(source), VAR(phi->ssa_var)); + } + } FOREACH_PHI_SOURCE_END(); + if (ssa->vars[phi->ssa_var].definition_phi != phi) { + FAIL(VARFMT " does not define this phi\n", VAR(phi->ssa_var)); + } + } FOREACH_PHI_END(); + + /* Blocks */ + for (i = 0; i < cfg->blocks_count; i++) { + zend_basic_block *block = &cfg->blocks[i]; + int *predecessors = &cfg->predecessors[block->predecessor_offset]; + int s, j; + + if (i != 0 && block->start < (block-1)->start + (block-1)->len) { + FAIL("Block %d start %d smaller previous end %d\n", + i, block->start, (block-1)->start + (block-1)->len); + } + if (i != cfg->blocks_count-1 && block->start + block->len > (block+1)->start) { + FAIL("Block %d end %d greater next start %d\n", + i, block->start + block->len, (block+1)->start); + } + + for (j = block->start; j < block->start + block->len; j++) { + if (cfg->map[j] != i) { + FAIL("Instr " INSTRFMT " not associated with block %d\n", INSTR(j), i); + } + } + + if (!(block->flags & ZEND_BB_REACHABLE)) { + if (ssa->blocks[i].phis) { + FAIL("Unreachable block %d has phis\n", i); + } + continue; + } + + for (s = 0; s < block->successors_count; s++) { + zend_basic_block *next_block; + if (block->successors[s] < 0) { + FAIL("Successor number %d of %d negative", s, i); + } + next_block = &cfg->blocks[block->successors[s]]; + if (!(next_block->flags & ZEND_BB_REACHABLE)) { + FAIL("Successor %d of %d not reachable\n", block->successors[s], i); + } + if (!is_in_predecessors(cfg, next_block, i)) { + FAIL("Block %d predecessors missing %d\n", block->successors[s], i); + } + } + + for (j = 0; j < block->predecessors_count; j++) { + if (predecessors[j] >= 0) { + int k; + zend_basic_block *prev_block = &cfg->blocks[predecessors[j]]; + if (!(prev_block->flags & ZEND_BB_REACHABLE)) { + FAIL("Predecessor %d of %d not reachable\n", predecessors[j], i); + } + if (!is_in_successors(prev_block, i)) { + FAIL("Block %d successors missing %d\n", predecessors[j], i); + } + for (k = 0; k < block->predecessors_count; k++) { + if (k != j && predecessors[k] == predecessors[j]) { + FAIL("Block %d has duplicate predecessor %d\n", i, predecessors[j]); + } + } + } + } + } + + return status; +} diff --git a/ext/opcache/Optimizer/zend_cfg.c b/ext/opcache/Optimizer/zend_cfg.c index 6ae5880c8f..9a7529aeee 100644 --- a/ext/opcache/Optimizer/zend_cfg.c +++ b/ext/opcache/Optimizer/zend_cfg.c @@ -441,6 +441,9 @@ int zend_build_cfg(zend_arena **arena, const zend_op_array *op_array, uint32_t b flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS; } break; + case ZEND_FUNC_GET_ARGS: + flags |= ZEND_FUNC_VARARG; + break; } } @@ -598,7 +601,8 @@ int zend_build_cfg(zend_arena **arena, const zend_op_array *op_array, uint32_t b /* Build CFG, Step 4, Mark Reachable Basic Blocks */ zend_mark_reachable_blocks(op_array, cfg, 0); - cfg->dynamic = (flags & ZEND_FUNC_INDIRECT_VAR_ACCESS); + cfg->dynamic = (flags & ZEND_FUNC_INDIRECT_VAR_ACCESS) != 0; + cfg->vararg = (flags & ZEND_FUNC_VARARG) != 0; if (func_flags) { *func_flags |= flags; @@ -646,9 +650,13 @@ int zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg) /* {{{ */ for (j = 0; j < cfg->blocks_count; j++) { if (blocks[j].flags & ZEND_BB_REACHABLE) { for (s = 0; s < blocks[j].successors_count; s++) { - zend_basic_block *b = blocks + blocks[j].successors[s]; - predecessors[b->predecessor_offset + b->predecessors_count] = j; - b->predecessors_count++; + /* SWITCH_STRING/LONG may have few following identical successors */ + if (s == 0 || blocks[j].successors[s-1] != blocks[j].successors[s]) { + zend_basic_block *b = blocks + blocks[j].successors[s]; + + predecessors[b->predecessor_offset + b->predecessors_count] = j; + b->predecessors_count++; + } } } } diff --git a/ext/opcache/Optimizer/zend_cfg.h b/ext/opcache/Optimizer/zend_cfg.h index ccff7d4425..b5b5683f12 100644 --- a/ext/opcache/Optimizer/zend_cfg.h +++ b/ext/opcache/Optimizer/zend_cfg.h @@ -93,6 +93,7 @@ typedef struct _zend_cfg { unsigned int split_at_calls : 1; unsigned int split_at_recv : 1; unsigned int dynamic : 1; /* accesses varables by name */ + unsigned int vararg : 1; /* uses func_get_args() */ } zend_cfg; /* Build Flags */ diff --git a/ext/opcache/Optimizer/zend_inference.c b/ext/opcache/Optimizer/zend_inference.c index 5234bc8ef6..1e52474897 100644 --- a/ext/opcache/Optimizer/zend_inference.c +++ b/ext/opcache/Optimizer/zend_inference.c @@ -282,7 +282,8 @@ int zend_ssa_find_false_dependencies(const zend_op_array *op_array, zend_ssa *ss } } else { for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) { - if (p->sources[j] >= 0 && ssa->vars[p->sources[j]].no_val) { + ZEND_ASSERT(p->sources[j] >= 0); + if (ssa->vars[p->sources[j]].no_val) { ssa_vars[p->sources[j]].no_val = 0; /* used indirectly */ zend_bitset_incl(worklist, p->sources[j]); } @@ -854,7 +855,8 @@ int zend_inference_calc_range(const zend_op_array *op_array, zend_ssa *ssa, int } } else { for (i = 0; i < ssa->cfg.blocks[p->block].predecessors_count; i++) { - if (p->sources[i] >= 0 && ssa->var_info[p->sources[i]].has_range) { + ZEND_ASSERT(p->sources[i] >= 0); + if (ssa->var_info[p->sources[i]].has_range) { /* union */ tmp->underflow |= ssa->var_info[p->sources[i]].range.underflow; tmp->min = MIN(tmp->min, ssa->var_info[p->sources[i]].range.min); @@ -3328,17 +3330,18 @@ int zend_infer_types_ex(const zend_op_array *op_array, const zend_script *script } UPDATE_SSA_TYPE(tmp, j); for (i = 0; i < blocks[p->block].predecessors_count; i++) { - if (p->sources[i] >= 0) { - zend_ssa_var_info *info = &ssa_var_info[p->sources[i]]; - if (info->type & MAY_BE_OBJECT) { - if (first) { - ce = info->ce; - is_instanceof = info->is_instanceof; - first = 0; - } else { - is_instanceof |= info->is_instanceof; - ce = join_class_entries(ce, info->ce, &is_instanceof); - } + zend_ssa_var_info *info; + + ZEND_ASSERT(p->sources[i] >= 0); + info = &ssa_var_info[p->sources[i]]; + if (info->type & MAY_BE_OBJECT) { + if (first) { + ce = info->ce; + is_instanceof = info->is_instanceof; + first = 0; + } else { + is_instanceof |= info->is_instanceof; + ce = join_class_entries(ce, info->ce, &is_instanceof); } } } @@ -3924,6 +3927,302 @@ void zend_inference_check_recursive_dependencies(zend_op_array *op_array) free_alloca(worklist, use_heap); } +int zend_may_throw(const zend_op *opline, zend_op_array *op_array, zend_ssa *ssa) +{ + uint32_t t1 = OP1_INFO(); + uint32_t t2 = OP2_INFO(); + + if (opline->op1_type == IS_CV) { + if (t1 & MAY_BE_UNDEF) { + switch (opline->opcode) { + case ZEND_UNSET_VAR: + case ZEND_ISSET_ISEMPTY_VAR: + if (opline->extended_value & ZEND_QUICK_SET) { + break; + } + return 1; + case ZEND_ISSET_ISEMPTY_DIM_OBJ: + case ZEND_ISSET_ISEMPTY_PROP_OBJ: + case ZEND_ASSIGN: + case ZEND_ASSIGN_DIM: + case ZEND_ASSIGN_REF: + case ZEND_BIND_GLOBAL: + case ZEND_FETCH_DIM_IS: + case ZEND_FETCH_OBJ_IS: + case ZEND_SEND_REF: + break; + default: + /* undefined variable warning */ + return 1; + } + } + } else if (opline->op1_type & (IS_TMP_VAR|IS_VAR)) { + if (t1 & (MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_ARRAY_OF_OBJECT|MAY_BE_ARRAY_OF_RESOURCE|MAY_BE_ARRAY_OF_ARRAY)) { + switch (opline->opcode) { + case ZEND_CASE: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: + case ZEND_FETCH_LIST: + case ZEND_QM_ASSIGN: + case ZEND_SEND_VAL: + case ZEND_SEND_VAL_EX: + case ZEND_SEND_VAR: + case ZEND_SEND_VAR_EX: + case ZEND_SEND_VAR_NO_REF: + case ZEND_SEND_VAR_NO_REF_EX: + case ZEND_SEND_REF: + case ZEND_SEPARATE: + case ZEND_END_SILENCE: + break; + default: + /* destructor may be called */ + return 1; + } + } + } + + if (opline->op2_type == IS_CV) { + if (t2 & MAY_BE_UNDEF) { + switch (opline->opcode) { + case ZEND_ASSIGN_REF: + break; + default: + /* undefined variable warning */ + return 1; + } + } + } else if (opline->op2_type & (IS_TMP_VAR|IS_VAR)) { + if (t2 & (MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_ARRAY_OF_OBJECT|MAY_BE_ARRAY_OF_RESOURCE|MAY_BE_ARRAY_OF_ARRAY)) { + switch (opline->opcode) { + case ZEND_ASSIGN: + break; + default: + /* destructor may be called */ + return 1; + } + } + } + + switch (opline->opcode) { + case ZEND_NOP: + case ZEND_IS_IDENTICAL: + case ZEND_IS_NOT_IDENTICAL: + case ZEND_QM_ASSIGN: + case ZEND_JMP: + case ZEND_CHECK_VAR: + case ZEND_MAKE_REF: + case ZEND_SEND_VAR: + case ZEND_BEGIN_SILENCE: + case ZEND_END_SILENCE: + case ZEND_SEND_VAL: + case ZEND_SEND_REF: + case ZEND_SEND_VAR_EX: + case ZEND_FREE: + case ZEND_SEPARATE: + case ZEND_TYPE_CHECK: + case ZEND_DEFINED: + case ZEND_ISSET_ISEMPTY_THIS: + case ZEND_COALESCE: + case ZEND_SWITCH_LONG: + case ZEND_SWITCH_STRING: + case ZEND_ISSET_ISEMPTY_VAR: + return 0; + case ZEND_INIT_FCALL: + /* can't throw, because call is resolved at compile time */ + return 0; + case ZEND_BIND_GLOBAL: + if ((opline+1)->opcode == ZEND_BIND_GLOBAL) { + return zend_may_throw(opline + 1, op_array, ssa); + } + return 0; + case ZEND_ADD: + if ((t1 & MAY_BE_ANY) == MAY_BE_ARRAY + && (t2 & MAY_BE_ANY) == MAY_BE_ARRAY) { + return 0; + } + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_DIV: + case ZEND_MOD: + if (!OP2_HAS_RANGE() || + (OP2_MIN_RANGE() <= 0 && OP2_MAX_RANGE() >= 0)) { + /* Division by zero */ + return 1; + } + /* break missing intentionally */ + case ZEND_SUB: + case ZEND_MUL: + case ZEND_POW: + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_SL: + case ZEND_SR: + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + !OP2_HAS_RANGE() || + OP2_MIN_RANGE() < 0; + case ZEND_CONCAT: + case ZEND_FAST_CONCAT: + return (t1 & (MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_BW_OR: + case ZEND_BW_AND: + case ZEND_BW_XOR: + if ((t1 & MAY_BE_ANY) == MAY_BE_STRING + && (t2 & MAY_BE_ANY) == MAY_BE_STRING) { + return 0; + } + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_BW_NOT: + return (t1 & (MAY_BE_NULL|MAY_BE_FALSE|MAY_BE_TRUE|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE)); + case ZEND_BOOL_NOT: + case ZEND_PRE_INC: + case ZEND_POST_INC: + case ZEND_PRE_DEC: + case ZEND_POST_DEC: + case ZEND_JMPZ: + case ZEND_JMPNZ: + case ZEND_JMPZNZ: + case ZEND_JMPZ_EX: + case ZEND_JMPNZ_EX: + case ZEND_BOOL: + case ZEND_JMP_SET: + return (t1 & MAY_BE_OBJECT); + case ZEND_BOOL_XOR: + return (t1 & MAY_BE_OBJECT) || (t2 & MAY_BE_OBJECT); + case ZEND_IS_EQUAL: + case ZEND_IS_NOT_EQUAL: + case ZEND_IS_SMALLER: + case ZEND_IS_SMALLER_OR_EQUAL: + case ZEND_CASE: + case ZEND_SPACESHIP: + if ((t1 & MAY_BE_ANY) == MAY_BE_NULL + || (t2 & MAY_BE_ANY) == MAY_BE_NULL) { + return 0; + } + return (t1 & (MAY_BE_OBJECT|MAY_BE_ARRAY_OF_ARRAY|MAY_BE_ARRAY_OF_OBJECT)) || (t2 & (MAY_BE_OBJECT|MAY_BE_ARRAY_OF_ARRAY|MAY_BE_ARRAY_OF_OBJECT)); + case ZEND_ASSIGN_ADD: + if (opline->extended_value != 0) { + return 1; + } + if ((t1 & MAY_BE_ANY) == MAY_BE_ARRAY + && (t2 & MAY_BE_ANY) == MAY_BE_ARRAY) { + return 0; + } + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_ASSIGN_DIV: + case ZEND_ASSIGN_MOD: + if (opline->extended_value != 0) { + return 1; + } + if (!OP2_HAS_RANGE() || + (OP2_MIN_RANGE() <= 0 && OP2_MAX_RANGE() >= 0)) { + /* Division by zero */ + return 1; + } + /* break missing intentionally */ + case ZEND_ASSIGN_SUB: + case ZEND_ASSIGN_MUL: + case ZEND_ASSIGN_POW: + if (opline->extended_value != 0) { + return 1; + } + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_ASSIGN_SL: + case ZEND_ASSIGN_SR: + if (opline->extended_value != 0) { + return 1; + } + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + !OP2_HAS_RANGE() || + OP2_MIN_RANGE() < 0; + case ZEND_ASSIGN_CONCAT: + if (opline->extended_value != 0) { + return 1; + } + return (t1 & (MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_ASSIGN_BW_OR: + case ZEND_ASSIGN_BW_AND: + case ZEND_ASSIGN_BW_XOR: + if (opline->extended_value != 0) { + return 1; + } + if ((t1 & MAY_BE_ANY) == MAY_BE_STRING + && (t2 & MAY_BE_ANY) == MAY_BE_STRING) { + return 0; + } + return (t1 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)) || + (t2 & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_ASSIGN: + case ZEND_UNSET_VAR: + return (t1 & (MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_ARRAY_OF_OBJECT|MAY_BE_ARRAY_OF_RESOURCE|MAY_BE_ARRAY_OF_ARRAY)); + case ZEND_ASSIGN_DIM: + return (t1 & (MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_TRUE|MAY_BE_STRING|MAY_BE_LONG|MAY_BE_DOUBLE)) || opline->op2_type == IS_UNUSED || + (t2 & (MAY_BE_UNDEF|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE)); + case ZEND_ROPE_INIT: + case ZEND_ROPE_ADD: + case ZEND_ROPE_END: + return t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT); + case ZEND_INIT_ARRAY: + case ZEND_ADD_ARRAY_ELEMENT: + return (opline->op2_type != IS_UNUSED) && (t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE)); + case ZEND_STRLEN: + return (t1 & MAY_BE_ANY) != MAY_BE_STRING; + case ZEND_COUNT: + return (t1 & MAY_BE_ANY) != MAY_BE_ARRAY; + case ZEND_RECV_INIT: + if (Z_CONSTANT_P(CRT_CONSTANT_EX(op_array, opline->op2, ssa->rt_constants))) { + return 1; + } + if (op_array->fn_flags & ZEND_ACC_HAS_TYPE_HINTS) { + uint32_t arg_num = opline->op1.num; + zend_arg_info *cur_arg_info; + + if (EXPECTED(arg_num <= op_array->num_args)) { + cur_arg_info = &op_array->arg_info[arg_num-1]; + } else if (UNEXPECTED(op_array->fn_flags & ZEND_ACC_VARIADIC)) { + cur_arg_info = &op_array->arg_info[op_array->num_args]; + } else { + return 0; + } + return ZEND_TYPE_IS_SET(cur_arg_info->type); + } else { + return 0; + } + case ZEND_FETCH_IS: + return (t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_ISSET_ISEMPTY_DIM_OBJ: + return (t1 & MAY_BE_OBJECT) || (t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT)); + case ZEND_FETCH_DIM_IS: + return (t1 & MAY_BE_OBJECT) || (t2 & (MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE)); + case ZEND_CAST: + switch (opline->extended_value) { + case IS_NULL: + return 0; + case _IS_BOOL: + return (t1 & MAY_BE_OBJECT); + case IS_LONG: + case IS_DOUBLE: + return (t1 & MAY_BE_OBJECT); + case IS_STRING: + return (t1 & (MAY_BE_ARRAY|MAY_BE_OBJECT)); + case IS_ARRAY: + return (t1 & MAY_BE_OBJECT); + case IS_OBJECT: + return (t1 & MAY_BE_ARRAY); + default: + return 1; + } + default: + return 1; + } +} + /* * Local variables: * tab-width: 4 diff --git a/ext/opcache/Optimizer/zend_inference.h b/ext/opcache/Optimizer/zend_inference.h index fecb124142..c10946a638 100644 --- a/ext/opcache/Optimizer/zend_inference.h +++ b/ext/opcache/Optimizer/zend_inference.h @@ -32,6 +32,9 @@ #define MAY_BE_RC1 (1<<27) /* may be non-reference with refcount == 1 */ #define MAY_BE_RCN (1<<28) /* may be non-reference with refcount > 1 */ +#define MAY_HAVE_DTOR \ + (MAY_BE_OBJECT|MAY_BE_RESOURCE \ + |MAY_BE_ARRAY_OF_ARRAY|MAY_BE_ARRAY_OF_OBJECT|MAY_BE_ARRAY_OF_RESOURCE) #define DEFINE_SSA_OP_HAS_RANGE(opN) \ static zend_always_inline zend_bool _ssa_##opN##_has_range(const zend_op_array *op_array, const zend_ssa *ssa, const zend_op *opline) \ @@ -263,6 +266,8 @@ void zend_func_return_info(const zend_op_array *op_array, int widening, zend_ssa_var_info *ret); +int zend_may_throw(const zend_op *opline, zend_op_array *op_array, zend_ssa *ssa); + END_EXTERN_C() #endif /* ZEND_INFERENCE_H */ diff --git a/ext/opcache/Optimizer/zend_optimizer.c b/ext/opcache/Optimizer/zend_optimizer.c index 89f5de800d..afd1c15597 100644 --- a/ext/opcache/Optimizer/zend_optimizer.c +++ b/ext/opcache/Optimizer/zend_optimizer.c @@ -53,6 +53,25 @@ void zend_optimizer_collect_constant(zend_optimizer_ctx *ctx, zval *name, zval* zend_hash_add(ctx->constants, Z_STR_P(name), &val); } +zend_uchar zend_compound_assign_to_binary_op(zend_uchar opcode) +{ + switch (opcode) { + case ZEND_ASSIGN_ADD: return ZEND_ADD; + case ZEND_ASSIGN_SUB: return ZEND_SUB; + case ZEND_ASSIGN_MUL: return ZEND_MUL; + case ZEND_ASSIGN_DIV: return ZEND_DIV; + case ZEND_ASSIGN_MOD: return ZEND_MOD; + case ZEND_ASSIGN_SL: return ZEND_SL; + case ZEND_ASSIGN_SR: return ZEND_SR; + case ZEND_ASSIGN_CONCAT: return ZEND_CONCAT; + case ZEND_ASSIGN_BW_OR: return ZEND_BW_OR; + case ZEND_ASSIGN_BW_AND: return ZEND_BW_AND; + case ZEND_ASSIGN_BW_XOR: return ZEND_BW_XOR; + case ZEND_ASSIGN_POW: return ZEND_POW; + EMPTY_SWITCH_DEFAULT_CASE() + } +} + int zend_optimizer_eval_binary_op(zval *result, zend_uchar opcode, zval *op1, zval *op2) /* {{{ */ { binary_op_type binary_op = get_binary_op(opcode); @@ -237,11 +256,53 @@ int zend_optimizer_update_op1_const(zend_op_array *op_array, zend_op *opline, zval *val) { + zend_op *target_opline; + switch (opline->opcode) { + case ZEND_JMPZ: + if (zend_is_true(val)) { + MAKE_NOP(opline); + } else { + opline->opcode = ZEND_JMP; + COPY_NODE(opline->op1, opline->op2); + opline->op2_type = IS_UNUSED; + } + zval_ptr_dtor_nogc(val); + return 1; + case ZEND_JMPNZ: + if (zend_is_true(val)) { + opline->opcode = ZEND_JMP; + COPY_NODE(opline->op1, opline->op2); + opline->op2_type = IS_UNUSED; + } else { + MAKE_NOP(opline); + } + zval_ptr_dtor_nogc(val); + return 1; + case ZEND_JMPZNZ: + if (zend_is_true(val)) { + target_opline = ZEND_OFFSET_TO_OPLINE(opline, opline->extended_value); + } else { + target_opline = ZEND_OP2_JMP_ADDR(opline); + } + ZEND_SET_OP_JMP_ADDR(opline, opline->op1, target_opline); + opline->op1_type = IS_UNUSED; + opline->extended_value = 0; + opline->opcode = ZEND_JMP; + zval_ptr_dtor_nogc(val); + return 1; case ZEND_FREE: MAKE_NOP(opline); zval_ptr_dtor_nogc(val); return 1; + case ZEND_SEND_VAR_EX: + case ZEND_FETCH_DIM_W: + case ZEND_FETCH_DIM_RW: + case ZEND_FETCH_DIM_FUNC_ARG: + case ZEND_FETCH_DIM_UNSET: + case ZEND_ASSIGN_DIM: + case ZEND_RETURN_BY_REF: + return 0; case ZEND_INIT_STATIC_METHOD_CALL: case ZEND_CATCH: case ZEND_FETCH_CONSTANT: @@ -305,6 +366,8 @@ int zend_optimizer_update_op2_const(zend_op_array *op_array, zend_op *opline, zval *val) { + zval tmp; + switch (opline->opcode) { case ZEND_ASSIGN_REF: case ZEND_FAST_CALL: @@ -331,7 +394,13 @@ int zend_optimizer_update_op2_const(zend_op_array *op_array, break; case ZEND_INIT_FCALL: REQUIRES_STRING(val); - zend_str_tolower(Z_STRVAL_P(val), Z_STRLEN_P(val)); + if (Z_REFCOUNT_P(val) == 1) { + zend_str_tolower(Z_STRVAL_P(val), Z_STRLEN_P(val)); + } else { + ZVAL_STR(&tmp, zend_string_tolower(Z_STR_P(val))); + zval_ptr_dtor_nogc(val); + val = &tmp; + } opline->op2.constant = zend_optimizer_add_literal(op_array, val); alloc_cache_slots_op2(op_array, opline, 1); break; @@ -482,6 +551,23 @@ void zend_optimizer_remove_live_range(zend_op_array *op_array, uint32_t var) } } +void zend_optimizer_remove_live_range_ex(zend_op_array *op_array, uint32_t var, uint32_t start) +{ + uint32_t i = 0; + + while (i < op_array->last_live_range) { + if (op_array->live_range[i].var == var + && op_array->live_range[i].start == start) { + op_array->last_live_range--; + if (i < op_array->last_live_range) { + memmove(&op_array->live_range[i], &op_array->live_range[i+1], (op_array->last_live_range - i) * sizeof(zend_live_range)); + } + break; + } + i++; + } +} + int zend_optimizer_replace_by_const(zend_op_array *op_array, zend_op *opline, zend_uchar type, @@ -973,13 +1059,24 @@ static void zend_optimize(zend_op_array *op_array, /* pass 11: * - Compact literals table */ - if (ZEND_OPTIMIZER_PASS_11 & ctx->optimization_level) { + if ((ZEND_OPTIMIZER_PASS_11 & ctx->optimization_level) && + (!(ZEND_OPTIMIZER_PASS_6 & ctx->optimization_level) || + !(ZEND_OPTIMIZER_PASS_7 & ctx->optimization_level))) { zend_optimizer_compact_literals(op_array, ctx); if (ctx->debug_level & ZEND_DUMP_AFTER_PASS_11) { zend_dump_op_array(op_array, 0, "after pass 11", NULL); } } + if ((ZEND_OPTIMIZER_PASS_13 & ctx->optimization_level) && + (!(ZEND_OPTIMIZER_PASS_6 & ctx->optimization_level) || + !(ZEND_OPTIMIZER_PASS_7 & ctx->optimization_level))) { + zend_optimizer_compact_vars(op_array); + if (ctx->debug_level & ZEND_DUMP_AFTER_PASS_13) { + zend_dump_op_array(op_array, 0, "after pass 13", NULL); + } + } + if (ZEND_OPTIMIZER_PASS_7 & ctx->optimization_level) { return; } @@ -1176,7 +1273,7 @@ int zend_optimize_script(zend_script *script, zend_long optimization_level, zend for (i = 0; i < call_graph.op_arrays_count; i++) { func_info = ZEND_FUNC_INFO(call_graph.op_arrays[i]); if (func_info) { - zend_dfa_optimize_op_array(call_graph.op_arrays[i], &ctx, &func_info->ssa); + zend_dfa_optimize_op_array(call_graph.op_arrays[i], &ctx, &func_info->ssa, func_info->call_map); } } @@ -1186,6 +1283,24 @@ int zend_optimize_script(zend_script *script, zend_long optimization_level, zend } } + if (ZEND_OPTIMIZER_PASS_11 & optimization_level) { + for (i = 0; i < call_graph.op_arrays_count; i++) { + zend_optimizer_compact_literals(call_graph.op_arrays[i], &ctx); + if (debug_level & ZEND_DUMP_AFTER_PASS_11) { + zend_dump_op_array(call_graph.op_arrays[i], 0, "after pass 11", NULL); + } + } + } + + if (ZEND_OPTIMIZER_PASS_13 & optimization_level) { + for (i = 0; i < call_graph.op_arrays_count; i++) { + zend_optimizer_compact_vars(call_graph.op_arrays[i]); + if (debug_level & ZEND_DUMP_AFTER_PASS_13) { + zend_dump_op_array(call_graph.op_arrays[i], 0, "after pass 13", NULL); + } + } + } + if (ZEND_OPTIMIZER_PASS_12 & optimization_level) { for (i = 0; i < call_graph.op_arrays_count; i++) { zend_adjust_fcall_stack_size_graph(call_graph.op_arrays[i]); diff --git a/ext/opcache/Optimizer/zend_optimizer.h b/ext/opcache/Optimizer/zend_optimizer.h index 69c89d7234..93354448ef 100644 --- a/ext/opcache/Optimizer/zend_optimizer.h +++ b/ext/opcache/Optimizer/zend_optimizer.h @@ -32,13 +32,13 @@ #define ZEND_OPTIMIZER_PASS_5 (1<<4) /* CFG based optimization */ #define ZEND_OPTIMIZER_PASS_6 (1<<5) /* DFA based optimization */ #define ZEND_OPTIMIZER_PASS_7 (1<<6) /* CALL GRAPH optimization */ -#define ZEND_OPTIMIZER_PASS_8 (1<<7) +#define ZEND_OPTIMIZER_PASS_8 (1<<7) /* SCCP (constant propagation) */ #define ZEND_OPTIMIZER_PASS_9 (1<<8) /* TMP VAR usage */ #define ZEND_OPTIMIZER_PASS_10 (1<<9) /* NOP removal */ #define ZEND_OPTIMIZER_PASS_11 (1<<10) /* Merge equal constants */ #define ZEND_OPTIMIZER_PASS_12 (1<<11) /* Adjust used stack */ -#define ZEND_OPTIMIZER_PASS_13 (1<<12) -#define ZEND_OPTIMIZER_PASS_14 (1<<13) +#define ZEND_OPTIMIZER_PASS_13 (1<<12) /* Remove unused variables */ +#define ZEND_OPTIMIZER_PASS_14 (1<<13) /* DCE (dead code elimination) */ #define ZEND_OPTIMIZER_PASS_15 (1<<14) /* Collect constants */ #define ZEND_OPTIMIZER_PASS_16 (1<<15) /* Inline functions */ diff --git a/ext/opcache/Optimizer/zend_optimizer_internal.h b/ext/opcache/Optimizer/zend_optimizer_internal.h index b5d4729100..aa37456b2b 100644 --- a/ext/opcache/Optimizer/zend_optimizer_internal.h +++ b/ext/opcache/Optimizer/zend_optimizer_internal.h @@ -23,6 +23,7 @@ #define ZEND_OPTIMIZER_INTERNAL_H #include "zend_ssa.h" +#include "zend_func_info.h" #define ZEND_OP1_LITERAL(opline) (op_array)->literals[(opline)->op1.constant] #define ZEND_OP1_JMP_ADDR(opline) OP_JMP_ADDR(opline, (opline)->op1) @@ -91,6 +92,7 @@ int zend_optimizer_replace_by_const(zend_op_array *op_array, zval *val); void zend_optimizer_remove_live_range(zend_op_array *op_array, uint32_t var); +void zend_optimizer_remove_live_range_ex(zend_op_array *op_array, uint32_t var, uint32_t start); void zend_optimizer_pass1(zend_op_array *op_array, zend_optimizer_ctx *ctx); void zend_optimizer_pass2(zend_op_array *op_array); void zend_optimizer_pass3(zend_op_array *op_array); @@ -98,15 +100,19 @@ void zend_optimize_func_calls(zend_op_array *op_array, zend_optimizer_ctx *ctx); void zend_optimize_cfg(zend_op_array *op_array, zend_optimizer_ctx *ctx); void zend_optimize_dfa(zend_op_array *op_array, zend_optimizer_ctx *ctx); int zend_dfa_analyze_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa, uint32_t *flags); -void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa); +void zend_dfa_optimize_op_array(zend_op_array *op_array, zend_optimizer_ctx *ctx, zend_ssa *ssa, zend_call_info **call_map); void zend_optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *ctx); void zend_optimizer_nop_removal(zend_op_array *op_array); void zend_optimizer_compact_literals(zend_op_array *op_array, zend_optimizer_ctx *ctx); +void zend_optimizer_compact_vars(zend_op_array *op_array); int zend_optimizer_is_disabled_func(const char *name, size_t len); zend_function *zend_optimizer_get_called_func( zend_script *script, zend_op_array *op_array, zend_op *opline, zend_bool rt_constants); uint32_t zend_optimizer_classify_function(zend_string *name, uint32_t num_args); void zend_optimizer_migrate_jump(zend_op_array *op_array, zend_op *new_opline, zend_op *opline); void zend_optimizer_shift_jump(zend_op_array *op_array, zend_op *opline, uint32_t *shiftlist); +zend_uchar zend_compound_assign_to_binary_op(zend_uchar opcode); +int sccp_optimize_op_array(zend_optimizer_ctx *ctx, zend_op_array *op_arrya, zend_ssa *ssa, zend_call_info **call_map); +int dce_optimize_op_array(zend_op_array *op_array, zend_ssa *ssa, zend_bool reorder_dtor_effects); #endif diff --git a/ext/opcache/Optimizer/zend_ssa.c b/ext/opcache/Optimizer/zend_ssa.c index 927ebb096c..b0eb87995d 100644 --- a/ext/opcache/Optimizer/zend_ssa.c +++ b/ext/opcache/Optimizer/zend_ssa.c @@ -13,6 +13,7 @@ | license@php.net so we can mail you a copy immediately. | +----------------------------------------------------------------------+ | Authors: Dmitry Stogov | + | Nikita Popov | +----------------------------------------------------------------------+ */ @@ -22,6 +23,7 @@ #include "zend_ssa.h" #include "zend_dump.h" #include "zend_inference.h" +#include "Optimizer/zend_optimizer_internal.h" static zend_bool dominates(const zend_basic_block *blocks, int a, int b) { while (blocks[b].level > blocks[a].level) { @@ -1059,15 +1061,16 @@ int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_ ssa_vars[phi->ssa_var].var = phi->var; ssa_vars[phi->ssa_var].definition_phi = phi; if (phi->pi >= 0) { - if (phi->sources[0] >= 0) { - zend_ssa_phi *p = ssa_vars[phi->sources[0]].phi_use_chain; - while (p && p != phi) { - p = zend_ssa_next_use_phi(ssa, phi->sources[0], p); - } - if (!p) { - phi->use_chains[0] = ssa_vars[phi->sources[0]].phi_use_chain; - ssa_vars[phi->sources[0]].phi_use_chain = phi; - } + zend_ssa_phi *p; + + ZEND_ASSERT(phi->sources[0] >= 0); + p = ssa_vars[phi->sources[0]].phi_use_chain; + while (p && p != phi) { + p = zend_ssa_next_use_phi(ssa, phi->sources[0], p); + } + if (!p) { + phi->use_chains[0] = ssa_vars[phi->sources[0]].phi_use_chain; + ssa_vars[phi->sources[0]].phi_use_chain = phi; } if (phi->has_range_constraint) { /* min and max variables can't be used together */ @@ -1084,15 +1087,16 @@ int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_ int j; for (j = 0; j < ssa->cfg.blocks[i].predecessors_count; j++) { - if (phi->sources[j] >= 0) { - zend_ssa_phi *p = ssa_vars[phi->sources[j]].phi_use_chain; - while (p && p != phi) { - p = zend_ssa_next_use_phi(ssa, phi->sources[j], p); - } - if (!p) { - phi->use_chains[j] = ssa_vars[phi->sources[j]].phi_use_chain; - ssa_vars[phi->sources[j]].phi_use_chain = phi; - } + zend_ssa_phi *p; + + ZEND_ASSERT(phi->sources[j] >= 0); + p = ssa_vars[phi->sources[j]].phi_use_chain; + while (p && p != phi) { + p = zend_ssa_next_use_phi(ssa, phi->sources[j], p); + } + if (!p) { + phi->use_chains[j] = ssa_vars[phi->sources[j]].phi_use_chain; + ssa_vars[phi->sources[j]].phi_use_chain = phi; } } } @@ -1161,6 +1165,420 @@ int zend_ssa_unlink_use_chain(zend_ssa *ssa, int op, int var) /* {{{ */ } /* }}} */ +void zend_ssa_remove_instr(zend_ssa *ssa, zend_op *opline, zend_ssa_op *ssa_op) /* {{{ */ +{ + if (ssa_op->result_use >= 0) { + zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->result_use); + ssa_op->result_use = -1; + ssa_op->res_use_chain = -1; + } + if (ssa_op->op1_use >= 0) { + if (ssa_op->op1_use != ssa_op->op2_use) { + zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->op1_use); + } else { + ssa_op->op2_use_chain = ssa_op->op1_use_chain; + } + ssa_op->op1_use = -1; + ssa_op->op1_use_chain = -1; + } + if (ssa_op->op2_use >= 0) { + zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->op2_use); + ssa_op->op2_use = -1; + ssa_op->op2_use_chain = -1; + } + + /* We let the caller make sure that all defs are gone */ + ZEND_ASSERT(ssa_op->result_def == -1); + ZEND_ASSERT(ssa_op->op1_def == -1); + ZEND_ASSERT(ssa_op->op2_def == -1); + + MAKE_NOP(opline); +} +/* }}} */ + +static inline zend_ssa_phi **zend_ssa_next_use_phi_ptr(zend_ssa *ssa, int var, zend_ssa_phi *p) /* {{{ */ +{ + if (p->pi >= 0) { + return &p->use_chains[0]; + } else { + int j; + for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) { + if (p->sources[j] == var) { + return &p->use_chains[j]; + } + } + } + ZEND_ASSERT(0); + return NULL; +} +/* }}} */ + +/* May be called even if source is not used in the phi (useful when removing uses in a phi + * with multiple identical operands) */ +static inline void zend_ssa_remove_use_of_phi_source(zend_ssa *ssa, zend_ssa_phi *phi, int source) /* {{{ */ +{ + zend_ssa_phi **cur = &ssa->vars[source].phi_use_chain; + while (*cur && *cur != phi) { + cur = zend_ssa_next_use_phi_ptr(ssa, source, *cur); + } + if (*cur) { + *cur = zend_ssa_next_use_phi(ssa, source, *cur); + } +} +/* }}} */ + +static void zend_ssa_remove_uses_of_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */ +{ + int source; + FOREACH_PHI_SOURCE(phi, source) { + zend_ssa_remove_use_of_phi_source(ssa, phi, source); + } FOREACH_PHI_SOURCE_END(); +} +/* }}} */ + +static void zend_ssa_remove_phi_from_block(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */ +{ + zend_ssa_block *block = &ssa->blocks[phi->block]; + zend_ssa_phi **cur = &block->phis; + while (*cur != phi) { + ZEND_ASSERT(*cur != NULL); + cur = &(*cur)->next; + } + *cur = (*cur)->next; +} +/* }}} */ + +static inline void zend_ssa_remove_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op) /* {{{ */ +{ + if (ssa_op->op1_def >= 0) { + zend_ssa_remove_uses_of_var(ssa, ssa_op->op1_def); + zend_ssa_remove_op1_def(ssa, ssa_op); + } + if (ssa_op->op2_def >= 0) { + zend_ssa_remove_uses_of_var(ssa, ssa_op->op2_def); + zend_ssa_remove_op2_def(ssa, ssa_op); + } + if (ssa_op->result_def >= 0) { + zend_ssa_remove_uses_of_var(ssa, ssa_op->result_def); + zend_ssa_remove_result_def(ssa, ssa_op); + } +} +/* }}} */ + +static inline void zend_ssa_remove_phi_source(zend_ssa *ssa, zend_ssa_phi *phi, int pred_offset, int predecessors_count) /* {{{ */ +{ + int j, var_num = phi->sources[pred_offset]; + + predecessors_count--; + if (pred_offset < predecessors_count) { + memmove(phi->sources + pred_offset, phi->sources + pred_offset + 1, (predecessors_count - pred_offset) * sizeof(uint32_t)); + } + + /* Check if they same var is used in a different phi operand as well, in this case we don't + * need to adjust the use chain (but may have to move the next pointer). */ + for (j = 0; j < predecessors_count; j++) { + if (phi->sources[j] == var_num) { + if (j < pred_offset) { + ZEND_ASSERT(phi->use_chains[pred_offset] == NULL); + return; + } + if (j >= pred_offset) { + phi->use_chains[j] = phi->use_chains[pred_offset]; + phi->use_chains[pred_offset] = NULL; + return; + } + } + } + + /* Variable only used in one operand, remove the phi from the use chain. */ + zend_ssa_remove_use_of_phi_source(ssa, phi, var_num); + phi->use_chains[pred_offset] = NULL; +} +/* }}} */ + +void zend_ssa_remove_phi(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */ +{ + ZEND_ASSERT(phi->ssa_var >= 0); + ZEND_ASSERT(ssa->vars[phi->ssa_var].use_chain < 0 + && ssa->vars[phi->ssa_var].phi_use_chain == NULL); + zend_ssa_remove_uses_of_phi_sources(ssa, phi); + zend_ssa_remove_phi_from_block(ssa, phi); + ssa->vars[phi->ssa_var].definition_phi = NULL; + phi->ssa_var = -1; +} +/* }}} */ + +void zend_ssa_remove_uses_of_var(zend_ssa *ssa, int var_num) /* {{{ */ +{ + zend_ssa_var *var = &ssa->vars[var_num]; + zend_ssa_phi *phi; + int use; + FOREACH_PHI_USE(var, phi) { + int i, end = NUM_PHI_SOURCES(phi); + for (i = 0; i < end; i++) { + if (phi->sources[i] == var_num) { + phi->use_chains[i] = NULL; + } + } + } FOREACH_PHI_USE_END(); + var->phi_use_chain = NULL; + FOREACH_USE(var, use) { + zend_ssa_op *ssa_op = &ssa->ops[use]; + if (ssa_op->op1_use == var_num) { + ssa_op->op1_use = -1; + ssa_op->op1_use_chain = -1; + } + if (ssa_op->op2_use == var_num) { + ssa_op->op2_use = -1; + ssa_op->op2_use_chain = -1; + } + if (ssa_op->result_use == var_num) { + ssa_op->result_use = -1; + ssa_op->res_use_chain = -1; + } + } FOREACH_USE_END(); + var->use_chain = -1; +} +/* }}} */ + +void zend_ssa_remove_block(zend_op_array *op_array, zend_ssa *ssa, int i) /* {{{ */ +{ + zend_basic_block *block = &ssa->cfg.blocks[i]; + zend_ssa_block *ssa_block = &ssa->blocks[i]; + int *predecessors; + zend_ssa_phi *phi; + int j, s; + + block->flags &= ~ZEND_BB_REACHABLE; + + /* Removes phis in this block */ + for (phi = ssa_block->phis; phi; phi = phi->next) { + zend_ssa_remove_uses_of_var(ssa, phi->ssa_var); + zend_ssa_remove_phi(ssa, phi); + } + + /* Remove instructions in this block */ + for (j = block->start; j < block->start + block->len; j++) { + if (op_array->opcodes[j].opcode == ZEND_NOP) { + continue; + } + + if (op_array->opcodes[j].result_type & (IS_TMP_VAR|IS_VAR)) { + zend_optimizer_remove_live_range_ex(op_array, op_array->opcodes[j].result.var, j + 1); + } + zend_ssa_remove_defs_of_instr(ssa, &ssa->ops[j]); + zend_ssa_remove_instr(ssa, &op_array->opcodes[j], &ssa->ops[j]); + } + + for (s = 0; s < block->successors_count; s++) { + zend_basic_block *next_block = &ssa->cfg.blocks[block->successors[s]]; + zend_ssa_block *next_ssa_block = &ssa->blocks[block->successors[s]]; + zend_ssa_phi *phi; + + /* Find at which predecessor offset this block is referenced */ + int pred_offset = -1; + predecessors = &ssa->cfg.predecessors[next_block->predecessor_offset]; + for (j = 0; j < next_block->predecessors_count; j++) { + if (predecessors[j] == i) { + pred_offset = j; + break; + } + } + ZEND_ASSERT(pred_offset != -1); + + /* For phis in successor blocks, remove the operands associated with this block */ + for (phi = next_ssa_block->phis; phi; phi = phi->next) { + if (phi->pi >= 0) { + if (phi->pi == i) { + zend_ssa_remove_uses_of_var(ssa, phi->ssa_var); + zend_ssa_remove_phi(ssa, phi); + } + } else { + ZEND_ASSERT(phi->sources[pred_offset] >= 0); + zend_ssa_remove_phi_source(ssa, phi, pred_offset, next_block->predecessors_count); + } + } + + /* Remove this predecessor */ + next_block->predecessors_count--; + if (pred_offset < next_block->predecessors_count) { + predecessors = &ssa->cfg.predecessors[next_block->predecessor_offset + pred_offset]; + memmove(predecessors, predecessors + 1, (next_block->predecessors_count - pred_offset) * sizeof(uint32_t)); + } + } + + /* Remove successors of predecessors */ + predecessors = &ssa->cfg.predecessors[block->predecessor_offset]; + for (j = 0; j < block->predecessors_count; j++) { + if (predecessors[j] >= 0) { + zend_basic_block *prev_block = &ssa->cfg.blocks[predecessors[j]]; + + for (s = 0; s < prev_block->successors_count; s++) { + if (prev_block->successors[s] == i) { + memmove(prev_block->successors + s, + prev_block->successors + s + 1, + sizeof(int) * (prev_block->successors_count - s - 1)); + prev_block->successors_count--; + s--; + } + } + } + } + + block->successors_count = 0; + block->predecessors_count = 0; + + /* Remove from dominators tree */ + if (block->idom >= 0) { + j = ssa->cfg.blocks[block->idom].children; + if (j == i) { + ssa->cfg.blocks[block->idom].children = block->next_child; + } else if (j >= 0) { + while (ssa->cfg.blocks[j].next_child >= 0) { + if (ssa->cfg.blocks[j].next_child == i) { + ssa->cfg.blocks[j].next_child = block->next_child; + break; + } + j = ssa->cfg.blocks[j].next_child; + } + } + } + block->idom = -1; + block->level = -1; + block->children = -1; + block->next_child = -1; +} +/* }}} */ + +static void propagate_phi_type_widening(zend_ssa *ssa, int var) /* {{{ */ +{ + zend_ssa_phi *phi; + FOREACH_PHI_USE(&ssa->vars[var], phi) { + if (ssa->var_info[var].type & ~ssa->var_info[phi->ssa_var].type) { + ssa->var_info[phi->ssa_var].type |= ssa->var_info[var].type; + propagate_phi_type_widening(ssa, phi->ssa_var); + } + } FOREACH_PHI_USE_END(); +} +/* }}} */ + +void zend_ssa_rename_var_uses(zend_ssa *ssa, int old, int new, zend_bool update_types) /* {{{ */ +{ + zend_ssa_var *old_var = &ssa->vars[old]; + zend_ssa_var *new_var = &ssa->vars[new]; + int use; + zend_ssa_phi *phi; + + ZEND_ASSERT(old >= 0 && new >= 0); + ZEND_ASSERT(old != new); + + /* Only a no_val is both variables are */ + new_var->no_val &= old_var->no_val; + + /* Update ssa_op use chains */ + FOREACH_USE(old_var, use) { + zend_ssa_op *ssa_op = &ssa->ops[use]; + + /* If the op already uses the new var, don't add the op to the use + * list again. Instead move the use_chain to the correct operand. */ + zend_bool add_to_use_chain = 1; + if (ssa_op->result_use == new) { + add_to_use_chain = 0; + } else if (ssa_op->op1_use == new) { + if (ssa_op->result_use == old) { + ssa_op->res_use_chain = ssa_op->op1_use_chain; + ssa_op->op1_use_chain = -1; + } + add_to_use_chain = 0; + } else if (ssa_op->op2_use == new) { + if (ssa_op->result_use == old) { + ssa_op->res_use_chain = ssa_op->op2_use_chain; + ssa_op->op2_use_chain = -1; + } else if (ssa_op->op1_use == old) { + ssa_op->op1_use_chain = ssa_op->op2_use_chain; + ssa_op->op2_use_chain = -1; + } + add_to_use_chain = 0; + } + + /* Perform the actual renaming */ + if (ssa_op->result_use == old) { + ssa_op->result_use = new; + } + if (ssa_op->op1_use == old) { + ssa_op->op1_use = new; + } + if (ssa_op->op2_use == old) { + ssa_op->op2_use = new; + } + + /* Add op to use chain of new var (if it isn't already). We use the + * first use chain of (result, op1, op2) that has the new variable. */ + if (add_to_use_chain) { + if (ssa_op->result_use == new) { + ssa_op->res_use_chain = new_var->use_chain; + new_var->use_chain = use; + } else if (ssa_op->op1_use == new) { + ssa_op->op1_use_chain = new_var->use_chain; + new_var->use_chain = use; + } else { + ZEND_ASSERT(ssa_op->op2_use == new); + ssa_op->op2_use_chain = new_var->use_chain; + new_var->use_chain = use; + } + } + } FOREACH_USE_END(); + old_var->use_chain = -1; + + /* Update phi use chains */ + FOREACH_PHI_USE(old_var, phi) { + int j; + zend_bool after_first_new_source = 0; + + /* If the phi already uses the new var, find its use chain, as we may + * need to move it to a different source operand. */ + zend_ssa_phi **existing_use_chain_ptr = NULL; + for (j = 0; j < ssa->cfg.blocks[phi->block].predecessors_count; j++) { + if (phi->sources[j] == new) { + existing_use_chain_ptr = &phi->use_chains[j]; + break; + } + } + + for (j = 0; j < ssa->cfg.blocks[phi->block].predecessors_count; j++) { + if (phi->sources[j] == new) { + after_first_new_source = 1; + } else if (phi->sources[j] == old) { + phi->sources[j] = new; + + /* Either move existing use chain to this source, or add the phi + * to the phi use chain of the new variables. Do this only once. */ + if (!after_first_new_source) { + if (existing_use_chain_ptr) { + phi->use_chains[j] = *existing_use_chain_ptr; + *existing_use_chain_ptr = NULL; + } else { + phi->use_chains[j] = new_var->phi_use_chain; + new_var->phi_use_chain = phi; + } + after_first_new_source = 1; + } + } + } + + /* Make sure phi result types are not incorrectly narrow after renaming. + * This should not normally happen, but can occur if we DCE an assignment + * or unset and there is an improper phi-indirected use lateron. */ + // TODO Alternatively we could rerun type-inference after DCE + if (update_types && (ssa->var_info[new].type & ~ssa->var_info[phi->ssa_var].type)) { + ssa->var_info[phi->ssa_var].type |= ssa->var_info[new].type; + propagate_phi_type_widening(ssa, phi->ssa_var); + } + } FOREACH_PHI_USE_END(); + old_var->phi_use_chain = NULL; +} +/* }}} */ + /* * Local variables: * tab-width: 4 diff --git a/ext/opcache/Optimizer/zend_ssa.h b/ext/opcache/Optimizer/zend_ssa.h index b8e5d8c3e8..c7724fa032 100644 --- a/ext/opcache/Optimizer/zend_ssa.h +++ b/ext/opcache/Optimizer/zend_ssa.h @@ -139,6 +139,41 @@ int zend_build_ssa(zend_arena **arena, const zend_script *script, const zend_op_ int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_array, zend_ssa *ssa); int zend_ssa_unlink_use_chain(zend_ssa *ssa, int op, int var); +void zend_ssa_remove_instr(zend_ssa *ssa, zend_op *opline, zend_ssa_op *ssa_op); +void zend_ssa_remove_phi(zend_ssa *ssa, zend_ssa_phi *phi); +void zend_ssa_remove_uses_of_var(zend_ssa *ssa, int var_num); +void zend_ssa_remove_block(zend_op_array *op_array, zend_ssa *ssa, int b); +void zend_ssa_rename_var_uses(zend_ssa *ssa, int old_var, int new_var, zend_bool update_types); + +static zend_always_inline void _zend_ssa_remove_def(zend_ssa_var *var) +{ + ZEND_ASSERT(var->definition >= 0); + ZEND_ASSERT(var->use_chain < 0); + ZEND_ASSERT(!var->phi_use_chain); + var->definition = -1; +} + +static zend_always_inline void zend_ssa_remove_result_def(zend_ssa *ssa, zend_ssa_op *ssa_op) +{ + zend_ssa_var *var = &ssa->vars[ssa_op->result_def]; + _zend_ssa_remove_def(var); + ssa_op->result_def = -1; +} + +static zend_always_inline void zend_ssa_remove_op1_def(zend_ssa *ssa, zend_ssa_op *ssa_op) +{ + zend_ssa_var *var = &ssa->vars[ssa_op->op1_def]; + _zend_ssa_remove_def(var); + ssa_op->op1_def = -1; +} + +static zend_always_inline void zend_ssa_remove_op2_def(zend_ssa *ssa, zend_ssa_op *ssa_op) +{ + zend_ssa_var *var = &ssa->vars[ssa_op->op2_def]; + _zend_ssa_remove_def(var); + ssa_op->op2_def = -1; +} + END_EXTERN_C() static zend_always_inline int zend_ssa_next_use(const zend_ssa_op *ssa_op, int var, int use) @@ -180,6 +215,95 @@ static zend_always_inline zend_bool zend_ssa_is_no_val_use(const zend_op *opline return 0; } +static zend_always_inline void zend_ssa_rename_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op) { + /* Rename def to use if possible. Mark variable as not defined otherwise. */ + if (ssa_op->op1_def >= 0) { + if (ssa_op->op1_use >= 0) { + zend_ssa_rename_var_uses(ssa, ssa_op->op1_def, ssa_op->op1_use, 1); + } + ssa->vars[ssa_op->op1_def].definition = -1; + ssa_op->op1_def = -1; + } + if (ssa_op->op2_def >= 0) { + if (ssa_op->op2_use >= 0) { + zend_ssa_rename_var_uses(ssa, ssa_op->op2_def, ssa_op->op2_use, 1); + } + ssa->vars[ssa_op->op2_def].definition = -1; + ssa_op->op2_def = -1; + } + if (ssa_op->result_def >= 0) { + if (ssa_op->result_use >= 0) { + zend_ssa_rename_var_uses(ssa, ssa_op->result_def, ssa_op->result_use, 1); + } + ssa->vars[ssa_op->result_def].definition = -1; + ssa_op->result_def = -1; + } +} + +#define NUM_PHI_SOURCES(phi) \ + ((phi)->pi >= 0 ? 1 : (ssa->cfg.blocks[(phi)->block].predecessors_count)) + +/* FOREACH_USE and FOREACH_PHI_USE explicitly support "continue" + * and changing the use chain of the current element */ +#define FOREACH_USE(var, use) do { \ + int _var_num = (var) - ssa->vars, next; \ + for (use = (var)->use_chain; use >= 0; use = next) { \ + next = zend_ssa_next_use(ssa->ops, _var_num, use); +#define FOREACH_USE_END() \ + } \ +} while (0) + +#define FOREACH_PHI_USE(var, phi) do { \ + int _var_num = (var) - ssa->vars; \ + zend_ssa_phi *next_phi; \ + for (phi = (var)->phi_use_chain; phi; phi = next_phi) { \ + next_phi = zend_ssa_next_use_phi(ssa, _var_num, phi); +#define FOREACH_PHI_USE_END() \ + } \ +} while (0) + +#define FOREACH_PHI_SOURCE(phi, source) do { \ + zend_ssa_phi *_phi = (phi); \ + int _i, _end = NUM_PHI_SOURCES(phi); \ + for (_i = 0; _i < _end; _i++) { \ + ZEND_ASSERT(_phi->sources[_i] >= 0); \ + source = _phi->sources[_i]; +#define FOREACH_PHI_SOURCE_END() \ + } \ +} while (0) + +#define FOREACH_PHI(phi) do { \ + int _i; \ + for (_i = 0; _i < ssa->cfg.blocks_count; _i++) { \ + phi = ssa->blocks[_i].phis; \ + for (; phi; phi = phi->next) { +#define FOREACH_PHI_END() \ + } \ + } \ +} while (0) + +#define FOREACH_BLOCK(block) do { \ + int _i; \ + for (_i = 0; _i < ssa->cfg.blocks_count; _i++) { \ + (block) = &ssa->cfg.blocks[_i]; \ + if (!((block)->flags & ZEND_BB_REACHABLE)) { \ + continue; \ + } +#define FOREACH_BLOCK_END() \ + } \ +} while (0) + +/* Does not support "break" */ +#define FOREACH_INSTR_NUM(i) do { \ + zend_basic_block *_block; \ + FOREACH_BLOCK(_block) { \ + uint32_t _end = _block->start + _block->len; \ + for ((i) = _block->start; (i) < _end; (i)++) { +#define FOREACH_INSTR_NUM_END() \ + } \ + } FOREACH_BLOCK_END(); \ +} while (0) + #endif /* ZEND_SSA_H */ /* diff --git a/ext/opcache/config.m4 b/ext/opcache/config.m4 index ded7f3dab2..7b500f023d 100644 --- a/ext/opcache/config.m4 +++ b/ext/opcache/config.m4 @@ -410,6 +410,10 @@ fi Optimizer/zend_inference.c \ Optimizer/zend_func_info.c \ Optimizer/zend_call_graph.c \ + Optimizer/sccp.c \ + Optimizer/scdf.c \ + Optimizer/dce.c \ + Optimizer/compact_vars.c \ Optimizer/zend_dump.c, shared,,-DZEND_ENABLE_STATIC_TSRMLS_CACHE=1,,yes) diff --git a/ext/opcache/config.w32 b/ext/opcache/config.w32 index 35c4645620..c2b757dd06 100644 --- a/ext/opcache/config.w32 +++ b/ext/opcache/config.w32 @@ -23,7 +23,7 @@ if (PHP_OPCACHE != "no") { zend_shared_alloc.c \ shared_alloc_win32.c", true, "/DZEND_ENABLE_STATIC_TSRMLS_CACHE=1"); - ADD_SOURCES(configure_module_dirname + "/Optimizer", "zend_optimizer.c pass1_5.c pass2.c pass3.c optimize_func_calls.c block_pass.c optimize_temp_vars_5.c nop_removal.c compact_literals.c zend_cfg.c zend_dfg.c dfa_pass.c zend_ssa.c zend_inference.c zend_func_info.c zend_call_graph.c zend_dump.c", "opcache", "OptimizerObj"); + ADD_SOURCES(configure_module_dirname + "/Optimizer", "zend_optimizer.c pass1_5.c pass2.c pass3.c optimize_func_calls.c block_pass.c optimize_temp_vars_5.c nop_removal.c compact_literals.c zend_cfg.c zend_dfg.c dfa_pass.c zend_ssa.c zend_inference.c zend_func_info.c zend_call_graph.c sccp.c scdf.c dce.c compact_vars.c zend_dump.c", "opcache", "OptimizerObj"); ADD_FLAG('CFLAGS_OPCACHE', "/I " + configure_module_dirname); diff --git a/ext/opcache/tests/ssa_bug_007.phpt b/ext/opcache/tests/ssa_bug_007.phpt new file mode 100644 index 0000000000..84d9e34b31 --- /dev/null +++ b/ext/opcache/tests/ssa_bug_007.phpt @@ -0,0 +1,23 @@ +--TEST-- +Incorrect CFG/SSA construction for SWITCH with few identical successors +--FILE-- + $value) { + switch ($key) { + case 'Trapped': + if ($value == null) { + $docInfo->$key = 1; + } + case 'CreationDate': + case 'ModDate': + $docInfo->$key = 2; + break; + } + } +} +?> +OK +--EXPECT-- +OK + -- 2.50.1