Journal Analyse de plage de valeurs dans Pythran

Sommaire

• La fonction _integ
• Implémentation de base
• Petits détails d'importance
• Conclusion

Demat'iNal,

Il y a quelques semaines, Pythran a gagné une analyse de plage de valeurs un peu plus solide que la précédente implémentation. Rien qui ne révolutionne la recherche, mais l'occasion pour moi d'explorer le sujet avec vous ici.

L'histoire commence en octobre 2018 avec l' issue #1029, alors que j'essayais de convertir des bouts de code de scikit-image à Pythran.

La fonction _integ

La fonction ci-dessous est extraite du fichier _hessian_det_appx.pyx, écrite en cython

# cython: wraparound=False
cdef inline Py_ssize_t _clip(Py_ssize_t x, Py_ssize_t low, Py_ssize_t high) nogil:
    if(x > high):
        return high
    if(x < low):
        return low
    return x

cdef inline cnp.double_t _integ(cnp.double_t[:, ::1] img, Py_ssize_t r, Py_ssize_t c, Py_ssize_t rl, Py_ssize_t cl) nogil:

    r = _clip(r, 0, img.shape[0] - 1)
    c = _clip(c, 0, img.shape[1] - 1)
    r2 = _clip(r + rl, 0, img.shape[0] - 1)
    c2 = _clip(c + cl, 0, img.shape[1] - 1)
    cdef cnp.double_t ans = img[r, c] + img[r2, c2] - img[r, c2] - img[r2, c]

    if (ans < 0):
        return 0
    return ans

On y retrouve les traditionnelles annotations de type, ainsi que des commentaires en début de fichier pour aider la génération de code.

La version Pythran est assez semblable

#pythran export _integ(float64[::], int, int, int, int)
import numpy as np
def _clip(x, low, high):
    assert 0 <= low <= high
    if x > high:
        return high
    if x < low:
        return low
    return x

def _integ(img, r, c, rl, cl):
    r = _clip(r, 0, img.shape[0] - 1)
    c = _clip(c, 0, img.shape[1] - 1)

    r2 = _clip(r + rl, 0, img.shape[0] - 1)
    c2 = _clip(c + cl, 0, img.shape[1] - 1)

    ans = img[r, c] + img[r2, c2] - img[r, c2] - img[r2, c]
    return max(0, ans)

On dégage les annotations de types et les aides à la génération de code. On spécifie la signature de la fonction à traduire (mais pas de la fonction auxiliaire), et on ajoute un assert qui prendra tout son sens plus tard dans le journal. Disons qu'il remplace le # cython: wraparound=False.

C'est le propos de ce journal : comment détecter qu'il n'y aura pas de wraparound sur les accès de tableau dans _integ, autrement dit que r, c et consorts sont positifs ou nuls. Pour cela, on va s'intéresser à l'analyse de plage de valeur.

note : en pythran, le comportement des assert est contrôlable à la compilation, par défaut ils dégagent

Implémentation de base

Depuis la PR #1522, Pythran est capable de calculer que la fonction clip renvoie une valeur toujours prositive ou nulle, et en déduit l'inutilité du wraparound.

L'analyse implémentée par Pythran est assez simple : elle travaille sur des intervalles à bornes numériques (non symboliques quoi); En gros on est capable de modéliser mais pas .

L'analyse est interprocédurale, mais indépendante du site d'appel : on ne sait rien sur les arguments en entrée (et c'est pour cela qu'on a besoin d'un assert pour ajouter des préconditions) mais on peut en déduire des informations sur la valeur de retour, par exemple qu'elle est toujours positive ou nulle.

Commençons par un exemple simple :

def foo(a):
    assert a > 0
    b = c = 10
    while a > 0:
        a -= 1
        b += 1
    if b == 9:
        print("wtf")
    if b == 10:
        print("wtf")
    if b == 11:
        print("ok")
    return a, b, c

L'analyse va suivre le flot de contrôle, donc on commence par le début (d'oh) de la fonction, où l'on ne sait rien : . Après le assert, on en sait un peu plus : . Après les affectations, on a en plus .

Arrive le while. On sait d'après nos conditions actuelles que le premier test sera vrai, donc on rentre et on exécute les deux assignations pour arriver à . On retombe sur le test, dont on ignore le résultat maintenant que est peut-être passé en dessous de 1. L'astuce ici est d'effectuer un tour de boucle, regarder l'évolution des variables et de les prolonger. Dans notre cas, après un tour supplémentaire, on aurait . En regardant le comportement des bornes, on en déduit la sur-estimation . On a donc l'état en sortie de boucle.

On arrive sur plusieurs if consécutifs. Et d'après l'état de nos variables, on sait que les deux premières conditions seront fausses, on ne les visite pas. On se contente d'un passage dans la dernière…

Pythran peut utiliser ces informations pour dégager le code mort, comme on peut le voir avec un pythran -P test.py qui afficher sur la sortie standard :

def foo(a):
    a_ = a
    assert (a_ > 0)
    b = 10
    while (a_ > 0):
        a_ -= 1
        b += 1
    if (b == 11):
        builtins.print('ok')
    return (a_, b, 10)

Petits détails d'importance

Utiliser une approche naïve a quelques avantages en termes de précision. Par exemple, sur le cas suivant :

def foo(a):
    if a > 12:
        b = 1
    else:
        b = 2
    if a > 1:
        b = 2
    return b

Le passage dans la branche true du premier test enregistre b = 1 mais aussi, en suivant les successeurs de cette branche, que b = 2 car le second test sera forcément vrai. En suivant ce « fil » on arrive toujours à return 2. En suivant la branche false on a b = 2 et ensuite, que le second test soit vrai ou pas, on arrive toujours à return 2, donc la fonction est simplifiable par Pythran en

def foo(a):
    return 2

Mais le parcours complet de chacun des fils peut être très couteux. Et si on se retrouve avec une grosse série de if, on a une jolie explosion combinatoire du nombre de fils à suivre… Si le nombre de fils explose, Pythran se rabat sur un algorithme plus simple mais moins précis.

Conclusion

Il parait que c'est bien de mettre une conclusion… Je dirais qu'ici, je trouve ça chouette que Pythran bénéficie comme ça d'une construction qui reste du Python valide !

Note: il existe une version plus ou moins équivalente de cet article, en anglais.