{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"id":[{"id":"https:\/\/ror.org\/03mb6wj31","id-type":"ROR","asserted-by":"publisher"},{"id":"https:\/\/www.isni.org\/000000041937028X","id-type":"ISNI","asserted-by":"publisher"},{"id":"https:\/\/www.wikidata.org\/entity\/Q1640731","id-type":"wikidata","asserted-by":"publisher"}],"name":"Universitat Polit\u00e8cnica de Catalunya","acronym":["UPC"]}],"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T10:28:06Z","timestamp":1785407286438,"version":"3.56.0"},"reference-count":0,"publisher":"Universitat Polit\u00e8cnica de Catalunya","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Dos de las limitaciones de rendimiento m\u00e1s importantes en los procesadores de hoy en d\u00eda provienen de las operaciones de memoria y de las dependencias de control. Para resolver estos problemas, las memorias cache y los predictores de salto son dos alternativas hardware bien conocidas que explotan, entre otros factores, el reuso temporal de memoria y la correlaci\u00f3n de saltos. En otras palabras, estas estructuras tratan de explotar la redundancia din\u00e1mica existente en los programas. Esta redundancia proviene parcialmente de la forma en que los programadores escriben c\u00f3digo, pero tambi\u00e9n de limitaciones existentes en el modelo de compilaci\u00f3n tradicional, lo cual introduce instrucciones de memoria y de salto innecesarias. Pensamos que los compiladores deber\u00edan ser muy agresivos optimizando programas, y por tanto ser capaces de eliminar una parte importante de esta redundancia. &lt;br\/&gt;Por otro lado, las optimizaciones aplicadas en tiempo de enlace o directamente al programa ejecutable final han recibido una atenci\u00f3n creciente en los \u00faltimos a\u00f1os, debido a limitaciones existentes en el modelo de compilaci\u00f3n tradicional. Incluso aplicando sofisticados an\u00e1lisis y transformaciones interprocedurales, un compilador tradicional no es capaz de optimizar un programa como una entidad completa. Un problema similar aparece aplicando t\u00e9cnicas de compilaci\u00f3n dirigidas por profiling: grandes proyectos se ven forzados a recompilar todos y cada uno de sus m\u00f3dulos para aprovechar dicha informaci\u00f3n. Por el contrario, seria m\u00e1s conveniente construir la aplicaci\u00f3n completa, instrumentarla para obtener informaci\u00f3n de profiling y optimizar entonces el binario final sin recompilar ni un solo fichero fuente.&lt;br\/&gt;En esta tesis presentamos nuevas t\u00e9cnicas de compilaci\u00f3n dirigidas por profiling para eliminar la redundancia encontrada en programas ejecutables a nivel binario (esto es, redundancia binaria), incluso aunque estos programas hayan sido compilados agresivamente con un nov\u00edsimo compilador comercial. Nuestras t\u00e9cnicas de eliminaci\u00f3n de redundancia est\u00e1n dise\u00f1adas para eliminar operaciones de memoria y de salto redundantes, que son las m\u00e1s importantes para mitigar los problemas de rendimiento que hemos mencionado. Estas propuestas est\u00e1n basadas en t\u00e9cnicas de eliminaci\u00f3n de redundancia parcial sensibles al camino de ejecuci\u00f3n. Los resultados muestran que aplicando nuestras optimizaciones, somos capaces de alcanzar una reducci\u00f3n del 14% en el tiempo de ejecuci\u00f3n de nuestro conjunto de programas.&lt;br\/&gt;En este trabajo tambi\u00e9n revisamos el problemas del an\u00e1lisis de alias en programas ejecutables, identificando el por qu\u00e9 la desambiguaci\u00f3n de memoria es uno de los puntos d\u00e9biles en la modificaci\u00f3n de c\u00f3digo objeto. Proponemos varios an\u00e1lisis para ser aplicados en el contexto de optimizadores binarios. Primero un an\u00e1lisis de alias estricto para descubrir dependencias de memoria sensibles al camino de ejecuci\u00f3n, el cual es usado en nuestras optimizaciones para la eliminaci\u00f3n de redundancias de memoria. &lt;br\/&gt;Seguidamente, dos an\u00e1lisis especulativos de posibles alias para detecci\u00f3n de independencias de memoria. Estos an\u00e1lisis est\u00e1n basados en introducir informaci\u00f3n especulativa en tiempo de an\u00e1lisis, lo que incrementa la precisi\u00f3n en partes importantes de c\u00f3digo manteniendo el an\u00e1lisis eficiente. Los resultados muestran que nuestras propuestas son altamente \u00fatiles para incrementar la desambiguaci\u00f3n de memoria de c\u00f3digo binario, lo que se traduce en oportunidades para aplicar optimizaciones. &lt;br\/&gt;Todos nuestros algoritmos, tanto de an\u00e1lisis como de optimizaci\u00f3n, han sido implementados en un optimizador binario, enfatizando los problemas m\u00e1s relevantes en la aplicaciones de nuestros algoritmos en c\u00f3digo ejecutable, sin la ayuda de gran parte de la informaci\u00f3n de alto nivel presente en compiladores tradicionales.<\/jats:p>\n                <jats:p>Two of the most important performance limiters in today's processor families comes from solving the memory wall and handling control dependencies. In order to address these issues, cache memories and branch predictors are well-known hardware proposals that take advantage of, among other things, exploiting both temporal memory reuse and branch correlation. In other words, they try to exploit the dynamic redundancy existing in programs. This redundancy comes partly from the way that programmers write source code, but also from limitations in the compilation model of traditional compilers, which introduces unnecessary memory and conditional branch instructions. We believe that today's optimizing compilers should be very aggressive in optimizing programs, and then they should be expected to optimize a significant part of this redundancy away.&lt;br\/&gt;On the other hand, optimizations performed at link-time or directly applied to final program executables have received increased attention in recent years, due to limitations in the traditional compilation model. First, even though performing sophisticated interprocedural analyses and transformations, traditional compilers do not have the opportunity to optimize  the program as a whole. A similar problem arises when applying profile-directe compilation techniques: large projects will be forced to re-build every source file to take advantage of profile information. By contrast, it would be more convenient to build the full application, instrument it to obtain profile data and then re-optimize the final binary without recompiling a single source file.&lt;br\/&gt;In this thesis we present new profile-guided compiler optimizations for eliminating the redundancy encountered on executable programs at binary level (i.e.: binary redundancy), even though these programs have been compiled with full optimizations using a state-ofthe- art commercial compiler. In particular, our Binary Redundancy Elimination (BRE) techniques are targeted at eliminating both redundant memory operations and redundant conditional branches, which are the most important ones for addressing the performance issues that we mentioned above in today's microprocessors. These new proposals are mainly based on Partial Redundancy Elimination (PRE) techniques for eliminating partial redundancies in a path-sensitive fashion. Our results show that, by applying our optimizations, we are able to achieve a 14% execution time reduction in our benchmark suite.&lt;br\/&gt;In this work we also review the problem of alias analysis at the executable program level, identifying why memory disambiguation is one of the weak points of object code modification. We then propose several alias analyses to be applied in the context of linktime or executable code optimizers. First, we present a must-alias analysis to recognize memory dependencies in a path- sensitive fashion, which is used in our optimization for eliminating redundant memory operations. Next, we propose two speculative may-alias data-flow algorithms to recognize memory independencies. These may-alias analyses are based on introducing unsafe speculation at analysis time, which increases alias precision on important portions of code while keeping the analysis reasonably cost-efficient. Our results show that our analyses prove to be very useful for increasing memory disambiguation accuracy of binary code, which turns out into opportunities for applying optimizations.&lt;br\/&gt;All our algorithms, both for the analyses and the optimizations, have been implemented within a binary optimizer, which overcomes most of the existing limitations of traditional source-code compilers. Therefore, our work also points out the most relevant issues of applying our algorithms at the executable code level, since most of the high-level information available in traditional compilers is lost.<\/jats:p>","DOI":"10.5821\/dissertation-2117-93300","type":"dissertation","created":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T02:18:40Z","timestamp":1689733120000},"approved":{"date-parts":[[2005,4,13]]},"source":"Crossref","is-referenced-by-count":0,"title":["Binary Redundancy Elimination"],"prefix":"10.5821","author":[{"given":"Manuel","family":"Fern\u00e1ndez G\u00f3mez","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"3865","container-title":[],"original-title":[],"contributor":[{"sequence":"additional","affiliation":[],"role":[null]}],"deposited":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T06:54:55Z","timestamp":1768546495000},"score":1,"resource":{"primary":{"URL":"https:\/\/hdl.handle.net\/2117\/93300"}},"subtitle":[],"editor":[{"given":"Roger","family":"Espasa Sans","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.5821\/dissertation-2117-93300","relation":{},"subject":[]}}