174819 2017-07-25 09:47:08 -0700 WebAssembly: generate even smaller binaries 2020-01-24 09:18:50 -0800 1 1 1 Unclassified WebKit JavaScriptCore WebKit Nightly Build Unspecified Unspecified NEW P2 Normal --- 174818 1 jfbastien webkit-unassigned fpizlo jfbastien keith_miller mark.lam msaboff saam oldest_to_newest 1331958 0 316368 jfbastien 2017-07-25 09:47:08 -0700 Created attachment 316368 allocations-graph.py This is a follow-up to #174818, there's plenty more size gains to be had! A few ideas in random order: 1. Don't make callee a patchpoint: it doesn't need to be a patchpoint, and uses up 4 instructions in every ARM64 function prologue. This is expensive with binaries that have 100k+ small functions, because we round up allocations and this patchpoint pushes us over the 32 byte jitAllocationGranule. Just encoding the pointer makes it still a big immediate, but we could add an indirection to use small values that encode well. 2. The jitAllocationGranule isn't needed for WebAssembly. It is required for GC to determine how to mark JIT stub routines, but WebAssembly doesn’t need alignment. That’s tricky to do though, because wasm and JS share the same executable allocator and granule is passed at construction time. Mixing aligned and non-aligned may have unexpected effects on JavaScript code (some μarch like aligned branches, etc). Maybe we should use a separate pool? 3. We don't use load and store pair on ARM, except in limited places (such as prologue / epilogue for fp and lr). This would take quite a while to teach B3 / Air about. I'm especially sad about the OMG tier up function's spills. 4. The bounds checks are bloaty on ARM. We need signaling memory. 5. If there’s no call, and no trapping op (memory, etc), then no fault can occur. No need to have the callee and codeblock on stack. We also have a separate TODO to just get rid of the codeblock outright for WebAssembly. 6. In register-only cases without spills, no need to save / restore fp / lr. We know whether that's the case in the stackcheck patchpoint, it could also handle fp / lr save / restore. 7. The js -> wasm entry point is bloaty and represents ~5% of all allocations on large games. Only one thing ever differs (the immediate), yet we generate a 96 or 128 bytes for each of them. We could tail-call to a common trampoline from it after the immediate. We could also append that code to each wasm function which is exported instead of having them separate. 8. A few of the functions see a pretty big size increase when compared to the original wasm binary. Here's some data (pre-#174818): BBQ blowup (executable allocated / wasm): | ARM64 BBQ 1 | ARM64 BBQ 2 | x86 BBQ 1 | x86 BBQ 2 average | 8.858 | 8.060 | 6.174 | 5.669 stddev | 6.406 | 5.654 | 5.239 | 5.064 min | 0.033 | 0.028 | 0.024 | 0.024 max | 72.000 | 57.600 | 56.000 | 56.000 Allocation types (bytes): | ARM64 BBQ 1 | ARM64 BBQ 2 | x86 BBQ 1 | x86 BBQ 2 unknown | 142880 | 154720 | 146144 | 146144 JS2wasm | 5285184 | 5285184 | 4844160 | 4844160 BBQ | 113392032 | 102043168 | 68447168 | 57660800 Allocation types (percentage of total allocation): | ARM64 BBQ 1 | ARM64 BBQ 2 | x86 BBQ 1 | x86 BBQ 2 unknown | 0% | 0% | 0% | 0% JS2wasm | 4% | 5% | 7% | 8% BBQ | 95% | 95% | 93% | 92% Biggest outliers compared to original (bytes): function index | ARM64 BBQ 1 | ARM64 BBQ 2 | x86 BBQ 1 | x86 BBQ 2 | original | blowup vs original 12586 | 288 | 224 | 224 | 224 | 4 | 72.000 x 103738 | 256 | 288 | 224 | 256 | 5 | 57.600 x 107915 | 256 | 288 | 224 | 256 | 5 | 57.600 x 65775 | 160 | 128 | 96 | 96 | 3 | 53.333 x 109396 | 160 | 128 | 96 | 96 | 3 | 53.333 x 109428 | 160 | 128 | 96 | 96 | 3 | 53.333 x 12322 | 256 | 256 | 224 | 256 | 5 | 51.200 x 111459 | 256 | 288 | 224 | 256 | 6 | 48.000 x 111462 | 256 | 288 | 224 | 256 | 6 | 48.000 x 111466 | 256 | 288 | 224 | 256 | 6 | 48.000 x Biggest outliers compared to original, with original > 100 (bytes): function index | ARM64 BBQ 1 | ARM64 BBQ 2 | x86 BBQ 1 | x86 BBQ 2 | original | blowup vs original 84672 | 4800 | 17472 | 3488 | 9824 | 832 | 21.000 x 12589 | 2624 | 51264 | 1344 | 49952 | 2994 | 17.122 x 12941 | 2656 | 51264 | 1376 | 49984 | 3012 | 17.020 x 12947 | 2656 | 51264 | 1376 | 49984 | 3012 | 17.020 x 12934 | 2688 | 51296 | 1376 | 49984 | 3020 | 16.985 x 36468 | 1824 | 1568 | 1408 | 1152 | 124 | 14.710 x 90394 | 1824 | 1600 | 1440 | 1184 | 129 | 14.140 x 90651 | 1824 | 1600 | 1440 | 1184 | 129 | 14.140 x 31620 | 1504 | 1312 | 1152 | 960 | 109 | 13.798 x 37056 | 1600 | 1408 | 1216 | 960 | 116 | 13.793 x Biggest difference between compiled functions (bytes): function index | ARM64 BBQ 1 | ARM64 BBQ 2 | x86 BBQ 1 | x86 BBQ 2 | original | compiled blowup 12589 | 2624 | 51264 | 1344 | 49952 | 2994 | 38.143 x 12934 | 2688 | 51296 | 1376 | 49984 | 3020 | 37.279 x 12941 | 2656 | 51264 | 1376 | 49984 | 3012 | 37.256 x 12947 | 2656 | 51264 | 1376 | 49984 | 3012 | 37.256 x 107548 | 3680 | 14144 | 2624 | 17952 | 2281 | 6.841 x 61194 | 3424 | 3104 | 768 | 576 | 479 | 5.944 x 11710 | 2560 | 2304 | 576 | 448 | 380 | 5.714 x 76474 | 1984 | 1792 | 448 | 352 | 249 | 5.636 x 94775 | 1984 | 1824 | 448 | 352 | 254 | 5.636 x 94920 | 4608 | 4128 | 1120 | 832 | 663 | 5.538 x (see attached script for how it was generated) 316368 2017-07-25 09:47:08 -0700 2017-07-25 09:47:08 -0700 allocations-graph.py allocations-graph.py text/x-python-script 8370 jfbastien IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCgppbXBvcnQgYXJncGFyc2UKaW1wb3J0IG1hdGgKaW1wb3J0 IHJlCgpkZWYgYXJndW1lbnRzKCk6CiAgICBwYXJzZXIgPSBhcmdwYXJzZS5Bcmd1bWVudFBhcnNl cihkZXNjcmlwdGlvbj0iQWxsb2NhdGlvbiBpbmZvIikKICAgIHBhcnNlci5hZGRfYXJndW1lbnQo J2ZpbGVuYW1lcycsIG5hcmdzPScrJywgaGVscD0nRmlsZSB3aXRoIGFsbG9jYXRpb24gZGF0YScp CiAgICBwYXJzZXIuYWRkX2FyZ3VtZW50KCctLW91dGxpZXJzJywgZGVmYXVsdD0xMCwgaGVscD0n TnVtYmVyIG9mIG91dGxpZXJzIHRvIHByaW50IG91dCcsIHR5cGU9aW50KQogICAgcGFyc2VyLmFk ZF9hcmd1bWVudCgnLS1taW4tc2l6ZScsIGRlZmF1bHQ9MTAwLCBoZWxwPSdOdW1iZXIgb2Ygb3V0 bGllcnMgdG8gcHJpbnQgb3V0IG1hdGNoaW5nIHRoaXMgc2l6ZScsIHR5cGU9aW50KQogICAgcmV0 dXJuIHBhcnNlci5wYXJzZV9hcmdzKCkKYXJncyA9IGFyZ3VtZW50cygpCgpkZWYgcGFyc2VfZmls ZShmaWxlbmFtZSk6CiAgICB3aGF0ID0gTm9uZQogICAgcHJldmlvdXMgPSB7ICd3aGVyZSc6ICd1 bmtub3duJywgJ2FsbG9jYXRpbmcnOiBOb25lLCAnZnVuY3Rpb24nOiBOb25lIH0KICAgIGVudHJp ZXMgPSBbXQogICAgd2l0aCBvcGVuKGZpbGVuYW1lKSBhcyBmaWw6CiAgICAgICAgZm9yIGxpbmUg aW4gZmlsOgogICAgICAgICAgICBpZiBub3Qgd2hhdDoKICAgICAgICAgICAgICAgIHdoYXQgPSBs aW5lLnN0cmlwKCkKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIGFsbG9jYXRp bmcgPSByZS5tYXRjaCgiXkFsbG9jYXRpbmcgKFswLTldKykgYnl0ZXMgb2YgZXhlY3V0YWJsZSBt ZW1vcnkgd2l0aCAoWzAtOV0rKSBieXRlcyBhbGxvY2F0ZWQsIChbMC05XSspIGJ5dGVzIHJlc2Vy dmVkLCBhbmQgKFswLTldKykgY29tbWl0dGVkLiQiLCBsaW5lKQogICAgICAgICAgICBiYnEgPSBy ZS5tYXRjaCgiXkJCUSBmdW5jdGlvbiwgKFswLTldKyksIChbMC05XSspJCIsIGxpbmUpCiAgICAg ICAgICAgIGpzMndhc20gPSByZS5tYXRjaCgiXkJCUSBqcyB0byB3YXNtLCAoWzAtOV0rKSwgKC4q KSQiLCBsaW5lKQoKICAgICAgICAgICAgaWYgYWxsb2NhdGluZzoKICAgICAgICAgICAgICAgIHBy ZXZpb3VzWydhbGxvY2F0aW5nJ10gPSBpbnQoYWxsb2NhdGluZy5ncm91cCgxKSkKICAgICAgICAg ICAgICAgIGVudHJpZXMuYXBwZW5kKHByZXZpb3VzKQogICAgICAgICAgICAgICAgcHJldmlvdXMg PSB7ICd3aGVyZSc6ICd1bmtub3duJywgJ2FsbG9jYXRpbmcnOiBOb25lLCAnZnVuY3Rpb24nOiBO b25lIH0KICAgICAgICAgICAgZWxpZiBiYnE6CiAgICAgICAgICAgICAgICBwcmV2aW91cyA9IHsg J3doZXJlJzogJ0JCUScsICdzaXplJzogaW50KGJicS5ncm91cCgyKSksICdhbGxvY2F0aW5nJzog Tm9uZSwgJ2Z1bmN0aW9uJzogaW50KGJicS5ncm91cCgxKSkgfQogICAgICAgICAgICBlbGlmIGpz Mndhc206CiAgICAgICAgICAgICAgICBwcmV2aW91cyA9IHsgJ3doZXJlJzogJ0pTMndhc20nLCAn c2lnbmF0dXJlJzoganMyd2FzbS5ncm91cCgyKSwgJ2FsbG9jYXRpbmcnOiBOb25lLCAnZnVuY3Rp b24nOiBpbnQoanMyd2FzbS5ncm91cCgxKSkgfQogICAgICAgICAgICBlbHNlOgogICAgICAgICAg ICAgICAgcmFpc2UgRXhjZXB0aW9uKCJDYW4ndCBtYXRjaDoge30iLmZvcm1hdChsaW5lKSkKICAg IGlmIHByZXZpb3VzWyd3aGVyZSddICE9ICd1bmtub3duJzoKICAgICAgICBlbnRyaWVzLmFwcGVu ZChwcmV2aW91cykKICAgIHJldHVybiB7ICd3aGF0Jzogd2hhdCwgJ2VudHJpZXMnOiBlbnRyaWVz IH0KCgpkZWYgYXZlcmFnZShjKToKICAgIHJldHVybiBmbG9hdChzdW0oYykpIC8gbGVuKGMpCmRl ZiBzdGRkZXYoYyk6CiAgICBhID0gYXZlcmFnZShjKQogICAgc3F1YXJlZF9kaWZmcyA9IFsoYiAt IGEpICoqIDIgZm9yIGIgaW4gY10KICAgIHJldHVybiBtYXRoLnNxcnQoc3VtKHNxdWFyZWRfZGlm ZnMpIC8gbGVuKHNxdWFyZWRfZGlmZnMpKQoKCmRlZiBhbmFseXplX29uZV9ydW4oZW50cmllcyk6 CiAgICBibG93dXAgPSBbXQogICAgYWxsb2NhdGlvbl90b3RhbCA9IDAKICAgIGFsbG9jYXRpbmdf Ynlfd2hlcmUgPSB7fQogICAganMyd2FzbV9zaWduYXR1cmVzID0ge30KICAgIGxvbmdlc3Rfc2ln bmF0dXJlID0gMAogICAgZnVuY3Rpb25fb3JpZ2luYWxfc2l6ZXMgPSB7fQogICAgZnVuY3Rpb25f Y29tcGlsZWRfc2l6ZXMgPSB7fQogICAgZm9yIGVudHJ5IGluIGVudHJpZXM6CiAgICAgICAgYWxs b2NhdGlvbl90b3RhbCArPSBlbnRyeVsnYWxsb2NhdGluZyddCiAgICAgICAgaWYgZW50cnlbJ3do ZXJlJ10gaW4gYWxsb2NhdGluZ19ieV93aGVyZToKICAgICAgICAgICAgYWxsb2NhdGluZ19ieV93 aGVyZVtlbnRyeVsnd2hlcmUnXV0gKz0gZW50cnlbJ2FsbG9jYXRpbmcnXQogICAgICAgIGVsc2U6 CiAgICAgICAgICAgIGFsbG9jYXRpbmdfYnlfd2hlcmVbZW50cnlbJ3doZXJlJ11dID0gZW50cnlb J2FsbG9jYXRpbmcnXQogICAgICAgIGlmIGVudHJ5Wyd3aGVyZSddID09ICdCQlEnOgogICAgICAg ICAgICBibG93dXAuYXBwZW5kKGZsb2F0KGVudHJ5WydhbGxvY2F0aW5nJ10pIC8gZW50cnlbJ3Np emUnXSkKICAgICAgICAgICAgZnVuY3Rpb25fb3JpZ2luYWxfc2l6ZXNbZW50cnlbJ2Z1bmN0aW9u J11dID0gZW50cnlbJ3NpemUnXQogICAgICAgICAgICBmdW5jdGlvbl9jb21waWxlZF9zaXplc1tl bnRyeVsnZnVuY3Rpb24nXV0gPSBlbnRyeVsnYWxsb2NhdGluZyddCiAgICAgICAgaWYgZW50cnlb J3doZXJlJ10gPT0gJ0pTMndhc20nOgogICAgICAgICAgICBsb25nZXN0X3NpZ25hdHVyZSA9IG1h eChsb25nZXN0X3NpZ25hdHVyZSwgbGVuKGVudHJ5WydzaWduYXR1cmUnXSkpCiAgICAgICAgICAg IGlmIGVudHJ5WydzaWduYXR1cmUnXSBpbiBqczJ3YXNtX3NpZ25hdHVyZXM6CiAgICAgICAgICAg ICAgICBqczJ3YXNtX3NpZ25hdHVyZXNbZW50cnlbJ3NpZ25hdHVyZSddXS5hcHBlbmQoZW50cnlb J2FsbG9jYXRpbmcnXSkKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIGpzMndhc21f c2lnbmF0dXJlc1tlbnRyeVsnc2lnbmF0dXJlJ11dID0gW2VudHJ5WydhbGxvY2F0aW5nJ11dCgog ICAgcmV0dXJuIHsKICAgICAgICAnYmxvd3VwJzogYmxvd3VwLAogICAgICAgICdhbGxvY2F0aW9u X3RvdGFsJzogYWxsb2NhdGlvbl90b3RhbCwKICAgICAgICAnYWxsb2NhdGluZ19ieV93aGVyZSc6 IGFsbG9jYXRpbmdfYnlfd2hlcmUsCiAgICAgICAgJ2pzMndhc21fc2lnbmF0dXJlcyc6IGpzMndh c21fc2lnbmF0dXJlcywKICAgICAgICAnbG9uZ2VzdF9zaWduYXR1cmUnOiBsb25nZXN0X3NpZ25h dHVyZSwKICAgICAgICAnZnVuY3Rpb25fb3JpZ2luYWxfc2l6ZXMnOiBmdW5jdGlvbl9vcmlnaW5h bF9zaXplcywKICAgICAgICAnZnVuY3Rpb25fY29tcGlsZWRfc2l6ZXMnOiBmdW5jdGlvbl9jb21w aWxlZF9zaXplcywKICAgIH0KCmRlZiBwcmludF9hbmFseXNpcyh3aGF0LCBhbmFseXNpcyk6CiAg ICBtYXhfd2hhdCA9IG1heChbNl0gKyBbbGVuKHcpIGZvciB3IGluIHdoYXRdKQogICAgd2hlcmVz ID0gW2FbJ2FsbG9jYXRpbmdfYnlfd2hlcmUnXS5rZXlzKCkgZm9yIGEgaW4gYW5hbHlzaXNdWzBd CiAgICBtYXhfd2hlcmUgPSBtYXgoWzEyXSArIFtsZW4odykgZm9yIHcgaW4gd2hlcmVzXSkKICAg IGhlYWRlciA9ICdcdHs6Pnt3aWR0aH19IHwgJy5mb3JtYXQoJycsIHdpZHRoPW1heF93aGVyZSkg ICArICcgfCAnLmpvaW4oWyd7Oj57d2lkdGh9fScuZm9ybWF0KHcsIHdpZHRoPW1heF93aGF0KSBm b3IgdyBpbiB3aGF0XSkKICAgIGJsb3d1cCA9ICdcbicuam9pbihbCiAgICAgICAgJ1x0ezo+e3dp ZHRofX0gfCAnLmZvcm1hdCgnYXZlcmFnZScsIHdpZHRoPW1heF93aGVyZSkgKyAnIHwgJy5qb2lu KFsnezo+e3dpZHRofS4zZn0nLmZvcm1hdChhdmVyYWdlKGFbJ2Jsb3d1cCddKSwgd2lkdGg9bWF4 X3doYXQpIGZvciBhIGluIGFuYWx5c2lzXSksCiAgICAgICAgJ1x0ezo+e3dpZHRofX0gfCAnLmZv cm1hdCgnc3RkZGV2Jywgd2lkdGg9bWF4X3doZXJlKSAgKyAnIHwgJy5qb2luKFsnezo+e3dpZHRo fS4zZn0nLmZvcm1hdChzdGRkZXYoYVsnYmxvd3VwJ10pLCAgd2lkdGg9bWF4X3doYXQpIGZvciBh IGluIGFuYWx5c2lzXSksCiAgICAgICAgJ1x0ezo+e3dpZHRofX0gfCAnLmZvcm1hdCgnbWluJywg d2lkdGg9bWF4X3doZXJlKSAgICAgKyAnIHwgJy5qb2luKFsnezo+e3dpZHRofS4zZn0nLmZvcm1h dChtaW4oYVsnYmxvd3VwJ10pLCAgICAgd2lkdGg9bWF4X3doYXQpIGZvciBhIGluIGFuYWx5c2lz XSksCiAgICAgICAgJ1x0ezo+e3dpZHRofX0gfCAnLmZvcm1hdCgnbWF4Jywgd2lkdGg9bWF4X3do ZXJlKSAgICAgKyAnIHwgJy5qb2luKFsnezo+e3dpZHRofS4zZn0nLmZvcm1hdChtYXgoYVsnYmxv d3VwJ10pLCAgICAgd2lkdGg9bWF4X3doYXQpIGZvciBhIGluIGFuYWx5c2lzXSkKICAgIF0pCiAg ICBwcmludCAnQkJRIGJsb3d1cCAoZXhlY3V0YWJsZSBhbGxvY2F0ZWQgLyB3YXNtKTpcbnt9XG57 fScuZm9ybWF0KGhlYWRlciwgYmxvd3VwKQogICAgdHlwZXMgPSAnXG4nLmpvaW4oWwogICAgICAg ICgnXHR7Oj57d2lkdGh9fSB8ICcuZm9ybWF0KHcsIHdpZHRoPW1heF93aGVyZSkgKwogICAgICAg ICAnIHwgJy5qb2luKFsnezo+e3dpZHRofX0nLmZvcm1hdChhWydhbGxvY2F0aW5nX2J5X3doZXJl J11bd10sIHdpZHRoPW1heF93aGF0KSBmb3IgYSBpbiBhbmFseXNpc10pKSBmb3IgdyBpbiB3aGVy ZXMKICAgIF0pCiAgICBwcmludCAnQWxsb2NhdGlvbiB0eXBlcyAoYnl0ZXMpOlxue31cbnt9Jy5m b3JtYXQoaGVhZGVyLCB0eXBlcykKICAgIHR5cGVfcGVyY2VudGFnZXMgPSAnXG4nLmpvaW4oWwog ICAgICAgICgnXHR7Oj57d2lkdGh9fSB8ICcuZm9ybWF0KHcsIHdpZHRoPW1heF93aGVyZSkgKwog ICAgICAgICAnIHwgJy5qb2luKFsnezo+e3dpZHRofS4wZn0lJy5mb3JtYXQoMTAwLiAqIGFbJ2Fs bG9jYXRpbmdfYnlfd2hlcmUnXVt3XSAvIGFbJ2FsbG9jYXRpb25fdG90YWwnXSwgd2lkdGg9bWF4 X3doYXQgLSAxKSBmb3IgYSBpbiBhbmFseXNpc10pKSBmb3IgdyBpbiB3aGVyZXMKICAgIF0pCiAg ICBwcmludCAnQWxsb2NhdGlvbiB0eXBlcyAocGVyY2VudGFnZSBvZiB0b3RhbCBhbGxvY2F0aW9u KTpcbnt9XG57fScuZm9ybWF0KGhlYWRlciwgdHlwZV9wZXJjZW50YWdlcykKCmRlZiBwcmludF9z aWduYXR1cmUoYW5hbHlzaXMpOgogICAgcHJpbnQgIkpTIHRvIHdhc20gc2lnbmF0dXJlczoiCiAg ICBmb3Igc2lnbmF0dXJlIGluIHNvcnRlZChsaXN0KGFuYWx5c2lzWydqczJ3YXNtX3NpZ25hdHVy ZXMnXSksIGtleT1sYW1iZGEgczogc3VtKGFuYWx5c2lzWydqczJ3YXNtX3NpZ25hdHVyZXMnXVtz XSksIHJldmVyc2U9VHJ1ZSk6CiAgICAgICAgY291bnQgPSBhbmFseXNpc1snanMyd2FzbV9zaWdu YXR1cmVzJ11bc2lnbmF0dXJlXQogICAgICAgIHByaW50ICJcdHs6Pnt3aWR0aH19OiB0b3RhbCB7 Oj45fSBjb3VudCB7Oj42fSBhdmVyYWdlIHs6PjYuMGZ9Ii5mb3JtYXQoCiAgICAgICAgICAgIHNp Z25hdHVyZSwgc3VtKGNvdW50KSwgbGVuKGNvdW50KSwgYXZlcmFnZShjb3VudCksIHdpZHRoPWFu YWx5c2lzWydsb25nZXN0X3NpZ25hdHVyZSddKQoKZGVmIGNvbXBhcmVfZnVuY3Rpb25fc2l6ZXMo d2hhdCwgb3JpZ2luYWwsIGNvbXBpbGVkKToKICAgIG1heF93aGF0ID0gbWF4KFs2XSArIFtsZW4o dykgZm9yIHcgaW4gd2hhdF0pCiAgICBoZWFkZXIgPSAnXHR7Oj4yMH0gfCAnLmZvcm1hdCgnZnVu Y3Rpb24gaW5kZXgnKSAgICsgJyB8ICcuam9pbihbJ3s6Pnt3aWR0aH19Jy5mb3JtYXQodywgd2lk dGg9bWF4X3doYXQpIGZvciB3IGluIHdoYXRdKQogICAgaW5kaWNlcyA9IHNvcnRlZChvcmlnaW5h bC5rZXlzKCkpCiAgICBhbmFseXplZCA9IFtdCiAgICBmb3IgaW5kZXggaW4gaW5kaWNlczoKICAg ICAgICBlID0gewogICAgICAgICAgICAnaW5kZXgnOiBpbmRleCwKICAgICAgICAgICAgJ29yaWdp bmFsJzogb3JpZ2luYWxbaW5kZXhdLAogICAgICAgICAgICAnY29tcGlsZWQnOiBbY1tpbmRleF0g Zm9yIGMgaW4gY29tcGlsZWRdLAogICAgICAgICAgICAnbWF4X2Jsb3d1cCc6IG1heChbMS4gKiBj W2luZGV4XSAvIG9yaWdpbmFsW2luZGV4XSBmb3IgYyBpbiBjb21waWxlZF0pLAogICAgICAgICAg ICAnYmlnZ2VzdF9jb21waWxlZF9ibG93dXAnOiAxLiAqIG1heChbY1tpbmRleF0gZm9yIGMgaW4g Y29tcGlsZWRdKSAvIG1pbihbY1tpbmRleF0gZm9yIGMgaW4gY29tcGlsZWRdKSwKICAgICAgICB9 CiAgICAgICAgYW5hbHl6ZWQuYXBwZW5kKGUpCiAgICBwcmludCAnQmlnZ2VzdCBvdXRsaWVycyBj b21wYXJlZCB0byBvcmlnaW5hbCAoYnl0ZXMpOlxue30gfCB7Oj57d2lkdGh9fSB8IHs6Pnt3aWR0 aH19Jy5mb3JtYXQoaGVhZGVyLCAnb3JpZ2luYWwnLCAnYmxvd3VwIHZzIG9yaWdpbmFsJywgd2lk dGg9bWF4X3doYXQpCiAgICBmb3IgYiBpbiBzb3J0ZWQoYW5hbHl6ZWQsIGtleT1sYW1iZGEgYTog YVsnbWF4X2Jsb3d1cCddLCByZXZlcnNlPVRydWUpWzphcmdzLm91dGxpZXJzXToKICAgICAgICBw cmludCAnXHR7Oj4yMH0gfCAnLmZvcm1hdChiWydpbmRleCddKSArICcgfCAnLmpvaW4oWyd7Oj57 d2lkdGh9fScuZm9ybWF0KGMsIHdpZHRoPW1heF93aGF0KSBmb3IgYyBpbiBiWydjb21waWxlZCdd XSkgKyAnIHwgezo+e3dpZHRofX0gfCB7Oj57d2lkdGh9LjNmfSB4Jy5mb3JtYXQoYlsnb3JpZ2lu YWwnXSwgYlsnbWF4X2Jsb3d1cCddLCB3aWR0aD1tYXhfd2hhdCkKICAgIHByaW50ICdCaWdnZXN0 IG91dGxpZXJzIGNvbXBhcmVkIHRvIG9yaWdpbmFsLCB3aXRoIG9yaWdpbmFsID4ge30gKGJ5dGVz KTpcbnt9IHwgezo+e3dpZHRofX0gfCB7Oj57d2lkdGh9fScuZm9ybWF0KGFyZ3MubWluX3NpemUs IGhlYWRlciwgJ29yaWdpbmFsJywgJ2Jsb3d1cCB2cyBvcmlnaW5hbCcsIHdpZHRoPW1heF93aGF0 KQogICAgZm9yIGIgaW4gc29ydGVkKFthIGZvciBhIGluIGFuYWx5emVkIGlmIGFbJ29yaWdpbmFs J10gPiBhcmdzLm1pbl9zaXplXSwga2V5PWxhbWJkYSBhOiBhWydtYXhfYmxvd3VwJ10sIHJldmVy c2U9VHJ1ZSlbOmFyZ3Mub3V0bGllcnNdOgogICAgICAgIHByaW50ICdcdHs6PjIwfSB8ICcuZm9y bWF0KGJbJ2luZGV4J10pICsgJyB8ICcuam9pbihbJ3s6Pnt3aWR0aH19Jy5mb3JtYXQoYywgd2lk dGg9bWF4X3doYXQpIGZvciBjIGluIGJbJ2NvbXBpbGVkJ11dKSArICcgfCB7Oj57d2lkdGh9fSB8 IHs6Pnt3aWR0aH0uM2Z9IHgnLmZvcm1hdChiWydvcmlnaW5hbCddLCBiWydtYXhfYmxvd3VwJ10s IHdpZHRoPW1heF93aGF0KQogICAgcHJpbnQgJ0JpZ2dlc3QgZGlmZmVyZW5jZSBiZXR3ZWVuIGNv bXBpbGVkIGZ1bmN0aW9ucyAoYnl0ZXMpOlxue30gfCB7Oj57d2lkdGh9fSB8IHs6Pnt3aWR0aH19 Jy5mb3JtYXQoaGVhZGVyLCAnb3JpZ2luYWwnLCAnY29tcGlsZWQgYmxvd3VwJywgd2lkdGg9bWF4 X3doYXQpCiAgICBmb3IgYiBpbiBzb3J0ZWQoYW5hbHl6ZWQsIGtleT1sYW1iZGEgYTogYVsnYmln Z2VzdF9jb21waWxlZF9ibG93dXAnXSwgcmV2ZXJzZT1UcnVlKVs6YXJncy5vdXRsaWVyc106CiAg ICAgICAgcHJpbnQgJ1x0ezo+MjB9IHwgJy5mb3JtYXQoYlsnaW5kZXgnXSkgKyAnIHwgJy5qb2lu KFsnezo+e3dpZHRofX0nLmZvcm1hdChjLCB3aWR0aD1tYXhfd2hhdCkgZm9yIGMgaW4gYlsnY29t cGlsZWQnXV0pICsgJyB8IHs6Pnt3aWR0aH19IHwgezo+e3dpZHRofS4zZn0geCcuZm9ybWF0KGJb J29yaWdpbmFsJ10sIGJbJ2JpZ2dlc3RfY29tcGlsZWRfYmxvd3VwJ10sIHdpZHRoPW1heF93aGF0 KQoKcnVucyA9IFtdCmZvciBmaWxlbmFtZSBpbiBhcmdzLmZpbGVuYW1lczoKICAgIHJ1bnMuYXBw ZW5kKHBhcnNlX2ZpbGUoZmlsZW5hbWUpKQoKaWYgbGVuKHJ1bnMpID09IDE6CiAgICBhbmFseXNp cyA9IGFuYWx5emVfb25lX3J1bihydW5zWzBdWydlbnRyaWVzJ10pCiAgICBwcmludF9hbmFseXNp cyhbcnVuc1swXVsnd2hhdCddXSwgW2FuYWx5c2lzXSkKICAgIHByaW50X3NpZ25hdHVyZShhbmFs eXNpcykKZWxzZToKICAgIHdoYXQgPSBbcnVuWyd3aGF0J10gZm9yIHJ1biBpbiBydW5zXQogICAg YW5hbHlzaXMgPSBbYW5hbHl6ZV9vbmVfcnVuKHJ1blsnZW50cmllcyddKSBmb3IgcnVuIGluIHJ1 bnNdCiAgICBwcmludF9hbmFseXNpcyh3aGF0LCBhbmFseXNpcykKICAgIGNvbXBhcmVfZnVuY3Rp b25fc2l6ZXMod2hhdCwgYW5hbHlzaXNbMF1bJ2Z1bmN0aW9uX29yaWdpbmFsX3NpemVzJ10sIFth WydmdW5jdGlvbl9jb21waWxlZF9zaXplcyddIGZvciBhIGluIGFuYWx5c2lzXSkK