Factorisation

Une fois normalisée, l'expression arithmétique doit être mise en forme (que ce soit pour rechercher une opération de type "multiply-add" ou pour extraire une ou plusieurs sous-parties invariantes par rapport aux indices de boucles). Il est donc nécessaire de "factoriser" les expressions selon certains critères (par exemple essayer d'obtenir des sous-expressions indépendantes des indices les plus internes - figure 7). Le critère que nous avons choisi dans un premier temps est la minimisation du nombre d'opérations d'un point de vue global ( peut être considéré comme une opération "multiply-add"). Cependant, nous pourrions (devrions ?) envisager de tenir compte simultanément d'autres critères tels que le nombre de registres utiles, ou encore la profondeur du chemin critique.

  
Figure 7: Critères de factorisation.

Plusieurs problèmes apparaissent à ce niveau :

• En se limitant aux critères proposés figure 7, une factorisation décidée à l'étape i peut empêcher une factorisation "meilleure" disponible seulement à une étape i+k ultérieure (sur la figure 8, la factorisation effectuée sur j à l'étape 1 interdit une factorisation sur k par la suite). Il pourrait donc être utile de conserver en mémoire un historique des transformations, et si une factorisation de niveau plus profond devient possible alors on "défait" (redistribution) les précédentes (mais pas toutes !?)...
• Il peut s'avérer par ailleurs nécessaire d'effectuer une renormalisation locale (pour conserver l'associativité et la distributivité par exemple). C'est le cas sur l'exemple de la figure 8 à l'étape 3.

  
Figure 8: Exemple de factorisations.

Factoriser une expression permet de diminuer le nombre d'opérations nécessaires pour son évaluation à deux niveaux :

• La factorisation d'une opération permet de passer de n à n-k opérations.
• En permettant d'extraire une sous-expression indépendante des indices de boucles les plus internes, la factorisation permet de remonter certains calculs (par exemple sur la figure 9 passage de l'étape 5 à l'étape 6).

  
Figure 9: Nombre d'opérations.