Further work on GCC's Adressing Mode Selection, GSoC 2016

gistfile1.txt

The goal of my GSoC 2016 project was to improve GCC's Addressing Mode Selection (AMS) pass by:
- Rewriting all of the original code to have a clearer structure and do some things more efficiently
- Fixing the bugs present in the original version
- Implementing further optimization methods to improve AMS's code-size reductions

By the end of the program, I managed to finish the rewrite, fix all but a few remaining bugs and improve the code-size
reductions by adding a new optimization (namely, tracing back the address register's values across previous basic blocks).

Some further work that needs to be done:
- Identifying and fixing any remaining bugs
- Adding further optimization methods or sub-passes (for example, displacement range fitting)
- Porting AMS to other architectures

The current state of the project can be found at https://github.com/erikvarga/gcc

All the commits I've made (these include work I've done after or before GSoC) can be viewed at
the following link:
https://github.com/erikvarga/gcc/commits/master?author=erikvarga

The commits I've made during GSoC 2016 are the following:
https://github.com/erikvarga/gcc/commit/bfa9e6296164b835ff14917c34f6509e0b08bfd8
https://github.com/erikvarga/gcc/commit/b72d42645cba18787bc8309b90a80b7dc038297d
https://github.com/erikvarga/gcc/commit/bd5ef557e0512b568d1116fb43abd9a8d1918f2f
https://github.com/erikvarga/gcc/commit/b9312456da7b54a1dee7000f35fdde53033ddd83
https://github.com/erikvarga/gcc/commit/30f47ccd5c07f83f906801c55a4dd96e2321f8a8
https://github.com/erikvarga/gcc/commit/89178fef84ee2b2919f44731b28e8c4434daa7a7
https://github.com/erikvarga/gcc/commit/6dc17e075d1d20e4f185d97452c2de371d6b3c78
https://github.com/erikvarga/gcc/commit/f131a163a2bff281dfc3cb7466cd3a4a1253c1fa
https://github.com/erikvarga/gcc/commit/a4031b5475d5c4c2685d6900ca1f93e7c7a2b74a
https://github.com/erikvarga/gcc/commit/c98fc78a4ed3a016408c497c875de6070513ad8b
https://github.com/erikvarga/gcc/commit/5dfb092ea97b84d5a42b54050b23a158993becc7
https://github.com/erikvarga/gcc/commit/4f7538431bd6392934acd96b99e2e79b642551e8
https://github.com/erikvarga/gcc/commit/e27f93ca0dbdeb78e13c1feacf16e6f1cd066302
https://github.com/erikvarga/gcc/commit/8f4ad4174169349b6d1f8de2a86e594e5cee1f1c
https://github.com/erikvarga/gcc/commit/af8ac0f6b328363c6383725aa51eb4974fabc953
https://github.com/erikvarga/gcc/commit/fcddfec1c622c95969a2444be81dcaa63c5d496b
https://github.com/erikvarga/gcc/commit/87b1b8b5541923ec856bd1cabe84e782b21d67fa
https://github.com/erikvarga/gcc/commit/942a4a67e50214ef82711675c817c24554064a57
https://github.com/erikvarga/gcc/commit/94bd378b82e90d235eaf2c97dd8a1840401cf31a
https://github.com/erikvarga/gcc/commit/54958b91ae242ba72b972d579ac8b1dfaac36731
https://github.com/erikvarga/gcc/commit/1a57824c912825452af80294020b185d11d91c45
https://github.com/erikvarga/gcc/commit/822d01fa90b4f686a16eab48731b7fad76e12312
https://github.com/erikvarga/gcc/commit/423c7720cda5124fd6574d69252840a4004e3f59
https://github.com/erikvarga/gcc/commit/cdc3d8594e124ea4b9037a482e24db36cf487563
https://github.com/erikvarga/gcc/commit/ca3ead770762e48b65402ab3a60ed0eb36093a42
https://github.com/erikvarga/gcc/commit/602f7b30217bc0dd1b05a345e45a7d780ad59243
https://github.com/erikvarga/gcc/commit/232342244a7407dd53709af350440405d1be2260
https://github.com/erikvarga/gcc/commit/922486d9cf9ac48a928f1501f3af48632f2600fb
https://github.com/erikvarga/gcc/commit/614eef4e777d988df7f7c7a869233ae6ab5e95a9
https://github.com/erikvarga/gcc/commit/935b5200e315a781fe04e269892296d0d3b9a0dc
https://github.com/erikvarga/gcc/commit/7204218903a6d9451d5d4bf216f0b1217c8aad7d
https://github.com/erikvarga/gcc/commit/efe65bf69db3df3583af0990b0f35662aed13d56
https://github.com/erikvarga/gcc/commit/372afcdf758668e462e984630117d5265048dbdb
https://github.com/erikvarga/gcc/commit/e58690c881507dd95b5b8657ba5fd48565955c00
https://github.com/erikvarga/gcc/commit/3182be38f9ea20fa6001f6a4537066409e511907
https://github.com/erikvarga/gcc/commit/9aebdb51a2cb56ee7aac2e7a7085e70031e0e70b
https://github.com/erikvarga/gcc/commit/3801335be4f01e7ddcdd9a39e6663acc69e11a3c
https://github.com/erikvarga/gcc/commit/e4c1538291cfa2c8ccb4eb44ee56c0ec5c224281
https://github.com/erikvarga/gcc/commit/52b39c06dd1783862547f48c989e130fb16bd425
https://github.com/erikvarga/gcc/commit/b129ad307f3e54f675dcd198b98f79117b9ccc5e
https://github.com/erikvarga/gcc/commit/f009ebfed0ed78839b5bc207c1459621c024c6d5
https://github.com/erikvarga/gcc/commit/284cdd8a21ae24a0172df24fbea70e1b30cec6fc
https://github.com/erikvarga/gcc/commit/8838d097bc06e8171b3230c95c6f4cc8fc273556
https://github.com/erikvarga/gcc/commit/e025c267529eb40a5ddc2bd9dfd04a90b7970c24
https://github.com/erikvarga/gcc/commit/b411f8e6d3c5d250caa1b1e3d349f807c3bbcb44
https://github.com/erikvarga/gcc/commit/86753acb102f2eccd6bd2960e46dbe62e1c27ae3
https://github.com/erikvarga/gcc/commit/b456532fe2ad9ef271ca87be77ccf1b2343a91a6
https://github.com/erikvarga/gcc/commit/3df10d78b4d889ff85866c9759f9fc88ef9910bd
https://github.com/erikvarga/gcc/commit/8ca0682c96de77b38a5507963578e0f5964b9838
https://github.com/erikvarga/gcc/commit/32e940a7cee3065ffa64f131887003340fda93e1
https://github.com/erikvarga/gcc/commit/10e613f5cdca1b8fe037910da176e95b055bdd80
https://github.com/erikvarga/gcc/commit/1fabb4cd345910e7e52d35e4007be96a6314bce7
https://github.com/erikvarga/gcc/commit/648a1d8b40c34fba377dc3de78ce5fd01b87235e
https://github.com/erikvarga/gcc/commit/7778e5cde5be8ed4d14b4a7f3b45448b8fa55701
https://github.com/erikvarga/gcc/commit/4efb398147d88e1ff14afb7943a4f871dea1a1b3
https://github.com/erikvarga/gcc/commit/6a3d5c366db4674d9d24cc4d63785763559716c5
https://github.com/erikvarga/gcc/commit/47003006d9ae9cd4fc56c71142c16c83c1c7a5e9
https://github.com/erikvarga/gcc/commit/211c6bdcbb5fb1a804d09da33355aebca97fdceb
https://github.com/erikvarga/gcc/commit/dd27aaf087b2744e65558df6dc0cd5363834ecbb
https://github.com/erikvarga/gcc/commit/077875dc7a9c489bd5301ba9c170c899d520fe1e
https://github.com/erikvarga/gcc/commit/7e2b570c214e14b553cb47bda4a80cc98d2b29f2
https://github.com/erikvarga/gcc/commit/1897f28165fbc8dcd0a7869ffcb5f8d64e195924
https://github.com/erikvarga/gcc/commit/3b82bc393f695e1089d8d1c7c1c749f93f0e9745
https://github.com/erikvarga/gcc/commit/007bd2f5a0e93e655b89a1146c2ff6d11fecc31e
https://github.com/erikvarga/gcc/commit/9c792941dec0d5bb779c790cfacd24b365299a57
https://github.com/erikvarga/gcc/commit/2e99c4f906880b058be78eb7892c72392add5ead
https://github.com/erikvarga/gcc/commit/ac22e088261ef094655ce99e43046570164418c3
https://github.com/erikvarga/gcc/commit/90e0ab7b401b66efbf799f91d39d719e387f448d
https://github.com/erikvarga/gcc/commit/beb13569038ec4c3fb1b3bb1a2ca92381392613f
https://github.com/erikvarga/gcc/commit/864ad68c0390d2ec2748b7066216ce893be89af7
https://github.com/erikvarga/gcc/commit/4a8adb7807b10e4953b549d70410baa0c3845f3e
https://github.com/erikvarga/gcc/commit/2bf061b2cdc30161d1bc10a9d6230e44f5a9e441
https://github.com/erikvarga/gcc/commit/1807641327d576fcbac51412cd7279566a8a0574
https://github.com/erikvarga/gcc/commit/97a9ae2131ba2a720cdb14da987327f91cc24d9d
https://github.com/erikvarga/gcc/commit/9cd862c74802390d288fec54522ab9f7208859a2
https://github.com/erikvarga/gcc/commit/43d4cb588697f5df3e10a60da29ee4b753dff1f2
https://github.com/erikvarga/gcc/commit/98c95600b625e8076cfefe0d5b1e131053aa2a4a
https://github.com/erikvarga/gcc/commit/a04bc51f398230386532e8eb58f09230dffc6f50
https://github.com/erikvarga/gcc/commit/7c6300f77719d022360c3d1623e439213ba97303
https://github.com/erikvarga/gcc/commit/abd1501c8bd43dddf3504a3fcf851619014e815c
https://github.com/erikvarga/gcc/commit/064375ecffe6d0be9febd70e14132ae45a865aa3
https://github.com/erikvarga/gcc/commit/2b2654e310d27bfc50ecffd45a0f789d5812f119
https://github.com/erikvarga/gcc/commit/2c210c80a63dc5de42d0dfe4987a04df4646c75f
https://github.com/erikvarga/gcc/commit/a1847dc5ce52e899b4e038abecde18142dd7d4f1
https://github.com/erikvarga/gcc/commit/35f30cdbca9c983ca2ec6965605ae82d69617fc2
https://github.com/erikvarga/gcc/commit/8a16400a44ef402477f48a4d715c8fc107ff00e3
https://github.com/erikvarga/gcc/commit/1422bad9f7878b398c23af8152118c464b9d46a1
https://github.com/erikvarga/gcc/commit/4b876be0ca14eb61f7e6995a0b543f4dc6485b85
https://github.com/erikvarga/gcc/commit/24e5ad09aa4c97776799623bc235024a034b536c
https://github.com/erikvarga/gcc/commit/18f3393be285596f299f5c06d18fa78ce705f4db
https://github.com/erikvarga/gcc/commit/b3721e19489e169053cb4df628a84c2a5dcad41f
https://github.com/erikvarga/gcc/commit/8fca37fbc87d8ecbfbeb911ba07bc3373ef8f5bc
https://github.com/erikvarga/gcc/commit/79954425b1e44e1df1fcf6187f37cf97d2157713
https://github.com/erikvarga/gcc/commit/73ce86cab055b1a4373433598eec1ce87cd8438c
https://github.com/erikvarga/gcc/commit/eb2c7370cce99d2245cfab2022f259acdef18395
https://github.com/erikvarga/gcc/commit/56ed0de7b3e414f9ca8a7f6ae63a946330dba38d
https://github.com/erikvarga/gcc/commit/d20455e28eaf36f46f33dc8491beb90cbd8ba730
https://github.com/erikvarga/gcc/commit/bbb13729ab8b5a0f2e511ec3dbcdd89ec27fedb8
https://github.com/erikvarga/gcc/commit/207599075e0a9a2ac9bd1321d66a81287558d05d
https://github.com/erikvarga/gcc/commit/6578e0e8c70862f0fc3797fa082a8aa5369e355d
https://github.com/erikvarga/gcc/commit/e8f95afb1c45a499d0f6a25f70fbdb5b2485902b
https://github.com/erikvarga/gcc/commit/5ecc623ea7fff4222343c61569304508cb3097b9
https://github.com/erikvarga/gcc/commit/50da0aaa0bb492f4818042964d60ed91f4c8dc53
https://github.com/erikvarga/gcc/commit/a129e650edb06f16cce3459caa3c46eb96768844
https://github.com/erikvarga/gcc/commit/741485dc7d268bb0f983d83b5633a6f59a9d290f
https://github.com/erikvarga/gcc/commit/fa1a1fd52c598f16db571b517652a9519c89058c
https://github.com/erikvarga/gcc/commit/c50eb4d1e0d4d6e11f2bf066ef529b087ffaf81d
https://github.com/erikvarga/gcc/commit/fe8eccf7f6cbfb867147669db90e89b17cd56330
https://github.com/erikvarga/gcc/commit/76a05ead5cd4d49479dc5afaf253bd3aad4fe2c9
https://github.com/erikvarga/gcc/commit/3d7dee69483b39b0730a5fac73e8530f100b8439
https://github.com/erikvarga/gcc/commit/fe148f34f1bef6bc351640a5f3929fed873eaa57
https://github.com/erikvarga/gcc/commit/dacf6896df49861bb909dc65f8e0ba25bf2b0d70
https://github.com/erikvarga/gcc/commit/462b9fe53678747f507a4cd9b3daa0d55a3992dd
https://github.com/erikvarga/gcc/commit/362b5fb80682670620dea02ae46db22575cf0781
https://github.com/erikvarga/gcc/commit/6b5d4cacb85c904e88f703ca57ed8b58eeadd41c
https://github.com/erikvarga/gcc/commit/87e37f6d2228efb617fdc1e2b06bd370bde206dc
https://github.com/erikvarga/gcc/commit/f1d3f410e9f555c32a039b1a49f347f1bf7a2947
https://github.com/erikvarga/gcc/commit/5420089028f4a952a5667c5553f11ce63a869f39
https://github.com/erikvarga/gcc/commit/a9d1c9e6262519411dd60f44fe67d0d6f076d432
https://github.com/erikvarga/gcc/commit/8f356dd21cb5a180fb453f983d41813fd21ec41b
https://github.com/erikvarga/gcc/commit/61c3a804ee08ee225d26eff70075f5ee9d68ca7f
https://github.com/erikvarga/gcc/commit/b8ff994d671290aeae33fae6df97c45874a73fe5
https://github.com/erikvarga/gcc/commit/cc59139308639900e9b7d1d89cda139a0e1bcaff
https://github.com/erikvarga/gcc/commit/3b18f1ac566b32ce6dd6d96d91b4badc18a65159
https://github.com/erikvarga/gcc/commit/14fb9d26594861380247a69a8ba4cb173c52607c
https://github.com/erikvarga/gcc/commit/aadabc2a3f4919180de2345df07c2a7d2ab04ddb
https://github.com/erikvarga/gcc/commit/e7663797433156c4046f2b37f1109706f3abec92
https://github.com/erikvarga/gcc/commit/4a009154c2046c64adaea08e8f96e4fb143cc21e
https://github.com/erikvarga/gcc/commit/ead988faff8573060c8c303166a10fac3e55008e
https://github.com/erikvarga/gcc/commit/331df4a9fdabfb09a6eacf145dfcbf66c44c9b43
https://github.com/erikvarga/gcc/commit/997053091717c1ca698993288616c49bbc57cc7f
https://github.com/erikvarga/gcc/commit/eaecf8b7a563f6e8ec39a07acb6679bb66d7fbb1
https://github.com/erikvarga/gcc/commit/afd5e0ca92b202d48fdc4122311f2c2ce2dfd69f
https://github.com/erikvarga/gcc/commit/51631291dc965d5b44570b9c052381695a7e39a8
https://github.com/erikvarga/gcc/commit/a8cbf1e2531a2634273b98bd8bb6df7a98ebbc1c
https://github.com/erikvarga/gcc/commit/ff46b058781fee6532260e110d7b47ae4b55580c
https://github.com/erikvarga/gcc/commit/caf3f2b610399f87bba49e72b89e6e1e4ad33506
https://github.com/erikvarga/gcc/commit/70a574c0f46cde790925ab2482bfda389db28ce6
https://github.com/erikvarga/gcc/commit/f493ef26c8f7c676497dce818405ae8d36f07656
https://github.com/erikvarga/gcc/commit/90b192ea0b1b7b3481fdd6ac606923952a16e084