Сети-Улманов алгоритам

У рачунарству, Сети-Улманов алгоритам је алгоритам за превођење синтаксног дрвета у машински код, који користи што је могуће мањи број инструкција. Именован је по својим изумитељима, Рави Сетију и Џефри Д. Улману.

ПрегледУреди

Када генерише код за аритметички израз, компајлер мора да одлучи који је најбољи начин да преведе израз у терминима броја коришћених инструкција, као и броја регистара који су потребни како би се проценило неко подстабло. Нарочито у случају када слободних регистара има мало, ред у коме се врши процена може бити важан због дужине генерисаног кода, зато што различит поредак може довести до "цурења" међувредности у меморију. Сети-Улманов алгоритам, (такође познат као Сети-Улманово набрајање) производи код који има најмањи могући број инструкција као и најмањи број складишних регистара (под претпоставком да се комутативност и асоцијативност примењују на операторе који се користе, али да закон дистрибуције нпр.   не важи). Приметићете да алгоритам успева иако ни комутативност ни асоцијативност не важе за задати израз, и стога, аритметичке трансформације се не могу применити.

Једноставни Сети-Улманов алгоритамУреди

Једноставни Сети-Улманов алгоритам ради као што је наведено (за РИСК архитектуру):

  1. Обиђи апстрактно синтаксно стабло у префиксном или постфиксном редоследу
    1. Сваком неконстантном чвору који је лист, додели 1 (другим речима, 1 регистар је потребан да чува променљиву/поље/итд.). Сваком константном чвору који је лист (RHS операције – литерали, вредности), додели 0.
    2. Сваком чвору који није лист n, додели број регистара који је потребан да се процени одговарајуће подстабло од n. Ако број регистара потребних у левом подстаблу (l) није једнак броју регистара који су потребни у десном подстаблу (r), број регистара потребних за тренутни чвор n је максимум(l, r). Ако је l == r, онда је број регистара потребних за тренутни чвор l + 1.
  2. Ширење кода
    1. Ако је број регистара који је потребан за рачунање левог подстабла чвора n већи од броја регистара за десно подстабло, онда се лево подстабло прво процењује (пошто је могуће да тај један регистар који је потребан десном подстаблу да чува резултат чини да лево подстабло цури). Ако је десном подстаблу потребно више регистара него левом подстаблу, десно подстабло се процењује прво. Ако оба подстабла захтевају подједнако регистара, онда је редослед процене небитан.

ПримерУреди

За аритметички израз  , апстрактно синтаксно стабло изгледа овако:

               =
              / \
             a   *
                / \
               /   \
              +     +
             / \   / \
            /   \ d   3
           +     *
          / \   / \
         b   c f   g

Да би наставили са алгоритмом, потребно је само да испитамо аритметичке операције  , другим речима потребно је само да гледамо на десно подстабло од знака '=':

               *
              / \
             /   \
            +     +
           / \   / \
          /   \ d   3
         +     *
        / \   / \
       b   c f   g

Сада почиње обилазак стабла (у префиксном редоследу), додељујемо број регистара потребних како би се проценила оба подстабла (приметити да је последњи сабирак у изразу   константа):

               *2
              / \
             /   \
            +2    +1
           / \   / \
          /   \ d1  30
         +1   *1
        / \   / \
       b1  c0f1  g0

Из овог стабла може се видети да је потребно још 2 регистра за рачунање левог подстабла '*', а само 1 регистар за рачунање десног подстабла. Чворовима 'c' и 'g' нису потребни регистри из следећих разлога: Ако је Т стабло лист, онда број регистара за израчунавање Т је 1 или 0 што зависи од тога да ли је Т лево или десно подстабло (пошто операција као што је add R1, A може да обради десну компоненту А без директног убацивања у регистар). Стога, требало би произвести код прво из левог подстабла, зато што се може доспети у ситуацију да постоје само 2 слободна регистра за рачунање целог израза. Ако је прво израчунато десно подстабло (коме је потребан само један регистар), био би потребан регистар да чува резултат десног подстабла док се израчунава лево подстабло (коме би опет било потребно 2 регистра), стога је потребно 3 регистра истовремено. Израчунавање прво лево подстабла захтева 2 регистра, али се резултат може чувати у једном, и пошто је десном подстаблу потребан само 1 регистар за израчунавање, рачунање израза се може одрадити само са преостала 2 регистра.

Напредни Сети-Улманов алгоритамУреди

У напредној верзији Сети-Улмановог алгоритма, аритметичке операције се прво трансформишу, користећи алгебарска својства коришћених оператора.

ЛитератураУреди

Види јошУреди

  • Stralerov broj, минимални број регистара који су потребни како би се израчунао израз без спољашњег простора

Спољашње везеУреди