Inférence de sous-programme

Question

Y a-t-il un article décrivant un algorithme / technique pour déduire les sous-programmes d'un programme compilé? En d'autres termes: existe-t-il un algorithme pour trouver des blocs de code qui apparaissent plus d'une fois dans le programme? Ces blocs pourraient faire réorganiser les instructions (sans changement de comportement du programme, bien sûr) afin qu'il soit plus susceptible de trouver un match.

Ce processus peut être considéré comme l'opposé de l'inlinaison du sous-programme qui est effectué par les compilateurs pour éviter les appels, mais augmentant la taille binaire.

Il me semble que c'est un problème théorique très dur.

Answer 1

Eh bien, c'est un problème intéressant. Les gens y ont travaillé. Une recherche rapide renvoie ces deux-là:

• Keith D. Cooper, Nathaniel McIntosh: Compression de code améliorée pour les processeurs RISC intégrés, PLDI 1999.

• Christopher W. Fraser, Eugene W. Myers, Alan L. Wendt: Analyser et comprimer le code d'assemblage, Sigplan avis, juin 1984.

Mais il y en a probablement beaucoup plus. Vous pourriez utiliser Google Scholar pour trouver des articles plus récents qui font référence à ces anciens.

Answer 2

Ce que vous recherchez s'appelle un "détecteur de clones". Vous pouvez le faire sur le code source ou le code d'objet. L'idée clé est de décider des points de variabilité que vous souhaitez accepter.

Tu peux Lisez à propos de notre clonedr Détecteur de clone, qui trouve du code dupliqué en comparant les arbres de syntaxe des fichiers source, en trouvant des correspondances exactes et quasi manquantes. Il fait sur de nombreux fichiers plutôt que dans un seul fichier source. C'est un peu comme une détection de «sous-expression courante», mais cela fonctionne sur les déclarations ainsi que sur le code exécutable. Lorsque le match n'est pas exact, il peut déterminer les paramètres pour le "sous-programme" (abstraction).

Voir mon papier Détection de clone à l'aide d'arbres de syntaxe abstraits pour une description algorithmique.

CLoneDr fait cela pour de nombreuses langues, en utilisant Analyseurs frontaux de la langue précis.

Le site décrit le fonctionnement de CLONEDR et compare CLONEDR avec un certain nombre d'autres outils de détection de clone.

CLONEDR ne gère pas la "réorganisation des instructions". Des méthodes moins évolutives qui trouvent des doublons en comparant les PDG peuvent le faire. Ceux-ci se rapprochent de la comparaison des graphiques de flux de données, ce qui pourrait être bon pour trouver des correspondances de code d'instructions de machine.

Answer 3

C'est peut-être stupide .. mais considérez "diff". Il en fait essentiellement une version restreinte de cela.