Thursday, August 29, 2013

Регистры: Как это сделаю я.

Это вторая статья про самодельный процессор, который я задумал.
Все статьи собраны тут: label-CPU

Каким мог бы быть регистровый файл моего garage-made процессора?

  1. Небольшим. Т. к. у нас FPGA, и к тому же надо как-то менее заратно переключать потоки.
  2. Дружественным к компилятору. Внутри процедуры хочется иметь много взаимозаменяемых прямо адресуемых регистров. При входе в процедуру хочется иметь автоматическое резервирование пространства в регистровом файле.
  3. Автоматическим. Операции резервирования/освобождения должен делать процессор, а не приложение.
  4. Универсальным. Все типы данных - integer ALU, FPU, SIMD processing unit - должны обрабатываться в одном универсальном регистровом файле.

В качестве первого приближения:
В режиме пользователя доступны 32 32-разрядных регистра r0..r31 (позже мы сделаем их 64-разрядными).
4  из них - глобальные и не вращаются:
  • r31 - Program Counter - указатель текущей исполняемой инструкции.
  • r30 - Stack Pointer - Вершина стека.
  • r29 - TLS Pointer - Указатель на статический блок, уникальный для каждого потока. 
  • r28 - Data Segment - Указатель на статические данные, разделяемые между потоками.
r0..r27 - вращающийся регистровый стек на 28 регистров.

xZbLboMwEEW/BildNOKdsCZpu2ilSFTq2oUJWDUYOU4D+fpCPYS4EKWLhm6Qfcce5tyxDIYT5tWjIGX2whNghm0mleGsDNtemmbzbIX6h5AKmijJQmFPE9hpkuScSVrqYsyLAmKpaVvO9GQlSWEgRDFhQ/WNJjLD4my/15+Apln3GssPVGQn6y5HAluyZ/L+W7JVuDJVzLZwfY1Ct78khVbBkfNcEwTs6FGvckuxDLTunYsEhCYxWnyc2+SsDScUnEs1yqsQWNuXznO17eFC9OSOgEL+ZgPSfxK2x9KFvWyE2Sq6G/h2yKiEqCRxOz80pwY3g5BQXSygx2qOGvAcpKhbw1XUcdEIPGYLnB765nqekrKzvjq4jKB36SlxD9sMkHecfTHCHrTsr89TwQfeNXj/RvDLIXyb1pxFm2nYXf/fGh+MsFst+yacht2zrvb9VuyWOYQ3J4E+XXmXoTvAP4e2BtDz+Xwaavdqq91btXrscl9MQx1M1etm2n8tv2NnvzPO+gs=

В режиме супервизора доступны еще несколько регистров состояния машины.
Один из этих регистров, содержит два пятибитовых поля: 
  • r_top (определяющее какой регистр будет считаться r0),
  • r_size (определяющее номер первого отсутствующего регистра.
На самом деле вращающихся регистров 32, но 4 последних не доступны приложению (они используются для обработки исключений).

Обращение к регистру происходит по такому правилу (псевдокод):
reg& get_register (int reg_index) {
  return
    reg_index >= 28 ?
       global_registers[reg_index-28] :
    reg_index >= r_size ?
       trap(NO_SUCH_REG, reg_index) :
       local_registers[(reg_index+r_top) & 0x1f];
}
7Vpdb9owFP01PDaKPyDhtdBtD5tUiUnbnqqMmBAtxMiYFvbrZ2qHEK5poxQnSMtLG19/xOeca/skZEAmq91nEa2X33jMsgH2492ATAcYh76v/h4C+7NAItJYh5AJbNOYbSohyXkm03U1OOd5zuayElvwrDrYOkoYCMzmUQajP9JYLs3k8KiMf2Fpsixug0ZjXbOR+2KMmC2ibSbvXkNYV+98XYcp1YG9CaBxMXJemcFfzleVgGCb9G91lovUTMNQ95uLmIlKKEvzP6c0kYcBmQjOpb5a7SYsO+hScK67fbpQe2RHsFzW6WDQP0fZ1kx9OgN8vSxTyWbraH4ov6hsMZ2YkGx38cYlHJVijK+YFPsD0bqWDpE3NEzrSGAYeSllJabF8kRRYppFhrXkOHQJU10YpHbUAUD9/WtLsMNRDdi+G9ghgD17bAX1ENVAjR2JPQaoHyftoKY1Uhw70hr5APZA6dAKcDxGHu4syxECyD3PawU4UXn+PnDqKNER3MyV5MXIb0In94s0yyY84/p0ItPhQzil16Bk1GkuEECJKLZB1zs9JR46Q47oCEJ3lQ3UAh16ISfQg7Bb6EMIvdYyuMZJ17HqIwv0dnb9Ia2puqu1Dl2daOm8C8YeCTpEDo1dayfeqJ7ozs486O5EYe9d73J1l7oj1TF0eKKdTQ7TbvO9mPGZ0amz2B0anTD0gs6MDrZ6v26tH+7U+mGL9XuSXOW/frHjt+QICAUsYMhC4IoFiwt8en1PdaSh2xyh71MTeI4ODwx9IiCDxQmbmWLOc/Xvnu1S+VMVfTUvXfqlSgb6of3bXKjh+VbMWTVNZSQSVjTDds5OSEG+JWGOQcGySKbP1YnYmDL3eOSpmmK5l/tn5OoJm1Ylv2XH3YWOGhXo+CrMEVg9raCxba6V30yrwlyfajXupQJSQSP+EanUda7ufVJ1KH5gySHLkutXHJQRPlXclowUyhj0MgIZ4RPSbck4hDKGvYznMhZ+51ZlLIxb72Pe0dH27HpLyzGwHI4XPPx/rSMGOoo6j1L44w+UpNv3rMT2m0o7yP1u3zsRettrl9iMbb8HQx2hsxUseZLHLD3Rc7OM1ofLteBztlFTuXezpinIbOwjkNnI1ecCpIlLbJakGCYp6crwFXrBHTU8G6R22lrGuit+pbh+KtMmtrCZMQh73a6oWxMb2Ey3ca9bY91UsfwWUzcvP5YlD/8A

При входе в процедуру r0 содержит адрес возврата, r1 и далее - параметры.
Пример вызова процедуры с двумя параметрами.

xZZNc4MgEIZ/jcc4uESj16Rpe+mpnemZClGmKA6SxvTXFyPGWOxMZpqPiwPvCuw+7AIeXhXNkyJV/iIpEx4g2nj4wQOIETLfVtj/EjLFaScFVthyyuqRpKUUmldjMZVlyVI90jZSjCerSMYc4TUlwlXfOdW5dQ6iQX9mPMv7ZYIo6Sy13vdzULYhW6FnBwk6c4M6GwRxJ+ytEAD0U5cjF76lLEaCYjX/Hru54dYPy+5DKsrUSBK8/DzlhNceXikpddcqmhUT7cb00Lthj39Yj3gUK/U5A3o3vojYWt8V00YglCqH3C7nmr1WJG37O5M3djBTmjV/ejDEZZKNyYJptW+R98QTH0UQWux2yBx3/d2wySHyE7yw/+Unm4xtDMRyzI5rDIGbho19msMcXA7Iid9EadZc1oYAL7M3WRl5FhrlEhwAJjiAywGQf/ztFANcAgN2MDgQ6pxUbZPKdFscglu6eYGXSmqiuWyLZpagCwCaB7F/RppA4k9midGjuDf8i1HoMDJBkCK4Tbks0BmVcqUiidwicaO+apEs8H3rI3YJuBVyTQIY7ksgnLgw8G0JLALnHLg1hGD6CHBT4RpHAIb7HQGhe0+ax5kwj5r2CYYbYvZYSCPVt0ERnXUnXIiG6Q4vs4Pt5O2M1z8=

Если процедуре требуются дополнительные локальные переменные, временные значения, или она будет делать вызовы других процедур, она должна зарезервировать под эти нужды несколько регистров. Для этого в начале процедуты компилятор вставит инструкцию save N, где N-число от 1 до 28.
Инструкция

  • вычтет N из r_top (чтобы изменить нумерацию регистров),
  • прибавит N к r_size, чтобы учесть увеличившийся размер регистрового файла,
  • в цикле, пока r_size>28, сохранит непоместившееся регистры в в стеке

Наш процессор - RISC, и поэтому процессор может делать один store за время исполнения инструкции.
Поэтому точный алгоритм работы save будет несколько иным: вначеле инструкция проверяет, есть ли невместившиеся регистры. Если есть, сохраняет один регистр и выполняет ветвление на себя. Если все регистры помещаются, процессор корректирует r_top и t_size и переходит к следующей инструкции.
Псевдокод:
void save (int count) {
   if (r_size + count > 28) {
      r_size += count;
      r_top -= count;
   } else {
      memory[--sp] = local_registers[(r_top + --r_size) & 0x1f];
      pc--;
   }
}
Когда в процессоре появится конвейер, мы оптимизируем исполнение этой инструкции для конвейерного случая. Но pc-- будет надежным решением, для восстановления состояния процессора, например после прерывания, которое может произойти между итерациями команды save.

После исполнения инструкции save N, регистр rN содержит адрес возврата, регистры rN+1 и далее - параметры процедуры. Регистры r0..rN-1 - локальные переменные.
Пример входа в процедуру, с тремя локальными регистрами:

zZjLjpswFIafJssgY2MI26TTmU1XU6lrNzhgFTAyzoTM09cEk0APkSJNMN1E8Du+nM/nJlZkVzSvilXZD5nwfIVR0qzItxXGG4TMbyuc/xFSJZJO8q1wFAmvR5KWMteiGot7WZZ8r0faQebjxSqWciC871kO1V8i0Zk9HA5v+hsXadZv44dxN1Lrc79Gwg/smOv1RcLdcIO6Mezblc5WiDf9yuXoBJ9SFiNB8Vp8jk95EPYYFt1vqRKuRlIuyj9DTORlRXZKSt09Fc2O5+299My7ad/vjF7pKF7qRyb0x/hg+dGeXfOiQoDZKROav1ds376fjMfYeVxp3tzd/GaScTMuC67VuYXds449FGJqgdspAeneT7frpciLSWT/lw2ul9iDMoswve5xs9k8WLOnEQQYIFDQfmOl2XNbGwKiTH/KyshrapRncMB4ggOGHDDyrn8bYsDPwEAABgChzljVPiZyfywuxm2hX5CtkpppIdt4WcfoCYBohDziP+AovT+M4MReuOmd50uE6GSs+G5iJUIPhMlMERLCCIFWzxohEVk2ODaQAAyPOQkQvCwBCguFCp0SoJh4MEniQXC7QuFP5gHoD3PkAYKXywMUVkrTmOWmo2nbL9Iwc9G5NFLtBAUdXvIVxx2HmI0JLJs1++BGIW4zpB951xbJwohjgGGyQD4DA6yNiut20SRRbgIDFMi7njBjM0knSqVbRyCgVC6RIiOAwVjACje9UoCHV7xYZpjoGQKnrhCYigk5LOIPMWRB3bKI/hcWIeykLrHhpn8IogViw7zePmlcxgbfnMjLXw==

Если процедура сама вызывает процедуру c X параметров, она должна разместить параметры в регистрах r1...rX и выполнить инструкцию call.
Инструкция call не обращается к памяти. Она копирует pc->r0; dest->pc;
Таким образом регистр r0 при вызове процедуры указывает на следующую исполняемую инструкцию после возврата.

zZjBjpswEIafhmOQsTGEa9Jte+lpK/XsBgesAkbGacg+fQ2YAB0iRWqAXiL4jfHM5xnPEIcc8/qLYmX6TcY8czCKa4d8cjDeI2R+G+H2l5AoEXeSZ4WLiHk1kbSUmRblVDzJouAnPdHOMpu+rGQJB8L7iWVQ/SFinVrjcDDoX7lI0n4ZL4i6kUrf+nfE/Mwumd61Eu6Ga9SNYW/fCTcreMOSxcSEDynziaB4JT6mZp6FtcOy+ylVzNVEykTxa8yJvDnkqKTU3VVeH3nWbEwPvZv2+cHo3VbFC/3MhN6M3yy7WNsV10ZgcawAuWsqNH8v2am5v5q4sZO50rx+aMHglwk2LnOu1a1B3hOPXBRgarHbKT7p7q/DJlPkRiS0z6WjTSbWB2Y5Jvc1BsfNhfV9noOPIQcE/DdemjUPlSEgiuS7LI28o0Z5BQeMZzhgyAEj9/7YGAN+BQYCMAAIVcrK5jKWp0veOneAcUEOSmqmhWySZhehFwCiIXKJ90Sg9PEwgRO5wb4Pnn8iRAEh4wLL18mVED2RJgtlSAAzxFs3Q0KybXLsIQGYHksSIHhbAnSmWgSrEqCYuPCQxKPkXguFB1BonpcwHpY4Bwje7hygsFKa9iwzbU3ThJGamY3OpJGqVVDQ8SbfcTwIiMWYwKKwchdFQGV4iGDBLorO1Aiy7gkJasQWZ0MIMLQ9AiyXS4SCj8dbvFlKzBRLf9VQ8E2pgBw2iYcIsqDrsgj/FxYBbCHa3FincPrhBrlhbocP+nZs9JcLefsD

Если процедура имеет результат, она помещает его в регистр rN+X (регистр последнего параметра).
Если процедура листовая и не использует локальных пременных, она может не делать save
Например:
int abs (int val) {
   return a < 0 ? -a : a;
}
abs: blt r1, 0, l1 ; blt-branch if less than
     neg r1
l1:  ret 0

Инструкция ret N является парной одновременно для call и save. Так же как call она не обращается к памяти. Она:
  • выбрасывает со стека N регистров (созданных командой save) r_top += N; r_size -= N;
  • и загружает r0->pc.
После возврата из процедуры регистр rX содержит результат.
А регистр r0 содержит адрес возврата из только что выполнившейся процедуры (то есть его можно считать испорченным)
Результат исполнения проwедуры abs

zZjBjpswEIafhmOQsTGEa9Ld7aWnrdSzFxywChgZpyH79DXBBNhJpEgN0EsEvzGe+WbGY+KQfdG8KVZlP2TCcwejpHHINwfjLULmtxXOX4RUiaSTPCscRcLriaSlzLWopmIsy5LHeqIdZD59WcVSDoT3mOVQ/SUSnVnjcDDo37lIs34ZL4i6kVqf+3ck/MCOud5cJNwNN6gbw962E85W8IYly4kJn1IWE0HxWnxOzTwIa4dl9yFVwtVEykX5e8yJvDhkr6TU3VXR7HneBqaH3k17vTN6tVXxUj8yoTfjD8uP1vaUqY82Cl+xnTKh+XvF4vb+ZJLGzuRK8+bu8oNTJtO4LLhW55Z3jztyUYCpZW6n+KS7Pw0RpsiNSGify0YRJtYBZiGm1zUGr82Fdfw2BB8DCAoB/42XZs1dbQiIMv0pKyNvqFGewQHjGxww5ICRe31sjAE/AwMBGACEOmNVe5nI+FhcnNvBvCA7JTXTQrYVs4nQEwDRELnEeyBR+nyYwIncYNsnzz8RojBReG32kmWKJUQP1MlMJRJAz71lSyQk61bHFhKA9TEnAYLXJUBhr1DBogQoJi7cJfGoupdC4QEUmhcVzIc59gGC19sHKGyV5nCWm0NNewQjDTOBzqWR6kVQ0HGQrzjuJMRsTG51Bd2+NEnUMhkBOsNdBDMeo+iNHkGW3SFBj1hjbwgBBuMBK2C7nCMVfDwO8WolcaNZ+oumgm9aBeSwSj5EkAVdlkX4v7AI4BHiUhvLNE4/XKE2zO3wOX8ZG/3hQl7+Ag==

Продолжение примера. Функция с двумя параметрами сохраняет результат abs в качестве своего резульата и возвращает управление:
    mov r1, r5
    ret 3
xZZNj5swEIZ/Dccgf/B53XTbXnraSj17wQGrBiPjbMj++ppgAmRYaaVmySUyr4M983jmxR7dV90PzZryl8q59AjKO49+8whJELK/vXC+EQot8kHCTjiKnLcLySgljWiWYqbqmmdmoR2UXC7WsIID4SVjEqp/RG5KFxyJJv0nF0U5boOjdJhpzXlcI+cHdpRmd5HIMN2hYY7geBDOTsDTlvUihHelqoWgeSvel2EehIvDsXtVOud6IUlR/51zos8e3WulzDCquj2X/cGM0IfXvn8we41V89p85oXA5f/G5NHFrhEgZnhnV3tqG5aJuvitGivvQqvA7VwEb1zbl27zssXGVcWNPvfIHXFCfBSR0GEfqdPh+TQdMkH+9W/l7IxHksxhLK5bTHnbgUv9AwwUYAAQ2pI1/TBX2bG65Pt0KoXhL5ZKr59sH1lNK8OMUH2x7FJ0B0ABTvwgSuIbQgH1KR55zDBRtIIo9acF/otTBMsFb1suMX1spSSQAKyVryRAyWMJhNAyrD9L62u9C9OO2TSlslILsMB+uQOOKPHjBN8aSAChhCudQe8BJARACqZf+y/ZFgCI9QccAgddBeCnNF4pi7tQWLEGum1jAGsgM9vbqjtigMEmxSrokl9SC1Hqo+mMH9AMEYJlwFt73drGDPDG+dvH6bJ2mZtdp+nzPw==
Возврат из процедуры не восстанавливает регистры, которые были сброшены в память инструкцией save. Поэтому вызывающая процедура должна выполнить инструкцию restore X Y для восстановления своего рабочего набора регистров. Операция restore:
  • выбрасывает со стека X регистров (r_top += N; r_size -= N)
  • убеждается, что регистровый файл содержит как минимум Y регистров.
void restore(int regs_to_drop, int active_regs) {
    if (r_count - regs_to_drop >= active_regs) {
        r_count -= regs_to_drop;
        r_top += regs_to_drop;
    } else {
        local_registers[(r_top + ++r_count) & 0x1f] = mem[sp++];
        pc--;
    }
}

В нашем примере нет регистров, которые нужно удалять, поэтому первый переметр инструкции restore будет 0.
Допустим, что вызывающей процедуре далее потребуется пять локальных регистров, поэтому сразу после инструкции call будет стоять инструкция restore 0, 5.
После ее исполнения из стека в регистр будет перемещен один недостающий регистр (т.к. перед инструкцией restore r_size был ==4):

xZfLjpswFIafhmWQL1y3Saftpqup1LUHHLAKGBlnQubpa4IJIYdIUyUDm8j+HexzPvv8GIfuyvaHYnX+S6a8cAhKW4d+cwiJEDK/nXC6ETIl0l7CVjiIlDcTSUtZaFFPxURWFU/0RNvLYjpZzTIOhNeEFVD9I1Kd2+BIMOo/ucjyYRkcxP1Io0/DHCnfs0OhN2eJ9MMt6scIDnvhZAU8LllNQviQspwIijfiYxrmXtg4LLs3qVKuJlIhqr/XnOiLQ3dKSt23ynbHi25jBuj9Y9/vjF5iVbzSn3nAs/m/s+JgY1cIENO8NbNtm5olosp+y9rIG98ocDkbwTtX5qHbvMxh47LkWp065JY4IS4KiG+xD9Rp3z+Om0yQe/lbfrXHA0lmMWaXJca8TcOmfgdDADHgZTGEdF0CESRAFiVAyboEfFgKxncKU6+du9CWmTQLaaQGYDnmQvNXA6XrH42fPgNHELlhhG8Lw4NQfASB0GcA8QGQjKm3zqGXAEBw5GIfOMMsADem4cyxeAqFGWugyxYGsAbiBtGQ71LVEQIMJilWQpf8krMQxC4a93iFYggQPAa8MdeIZcwAr54/BvmDzJuc1V0zlcmhPCe7hTDoVknNtJDddWoTozsoZoDdpeMZq/TGihjpuPTin1eI6AwiEl+V1EOcZi5UvNFS8fT2PfLZk/MYG7z2aySgkIj3vwb6GANws/h6AzXd8RZ/Hrv6zqIv/wA=

Стеково-регистровая модель позволяет исключить копирования регистров при передаче результата одной процедуры в качестве параметра другой процедуры.
Но об этом в следующий раз.

Специальные случаи

Если последний параметр процедуры out или in-out, результат возвращается не в последенем парметре, а в регистре, следующем за последним параметром.

Если процедура имеет более 27 парметров, первые 27 параметров (и адрес возврата) располагаются в регистрах, остальные - в стеке. Такая процедура обращается к стековым парметрам с помощью инструкции ld [sp+offset], rN.

Если процедура имеет более 28 локальных и временных переменных,
  • она начинается с инструкции save 28, которая сбрасывает в стек содержимое всех регистров caller-а (включая адрес возврата),
  • затем она вычитает из sp размер своего стекового кадра,
  • и выполняется используя 28 регистров и стековый кадр, как на обычной регистровой машине
  • затем она загружает адрес возврата ld [sp+frame_size], r27;
  • прибавляет к sp размер стекового кадра + 1 (чтобы выбросить кадр и адрес возврата),
  • выполняет инструкцию ret 27, которая очистит регистровый файл (превратив r27 в r0) и сделает переход на адрес возврата r0->pc
Если локальные переменные превышают 28, но среди них можно выделить локальные группы (имеют блочную область видмости), эти блоки кода могут обрамляться save N / restore N M, чтобы эффективно утилизировать регистровый файл для самых внутренних локалов.

Резюме


  • Имея два служебных регистра r_top и r_size. Мы можем организовать регистрово-стековую машину, которая эффективно сочетает максимальную производительность RISC-архитектуры при вычислениях внутри процедуры с эффективным использованием регистровой и стековой памяти, присущих стековым машинам.
  • При вызовах процедур обмен с памятью минимизирован.
  • Благодаря экономному использованию регистров, мы можем сократить их количество и упростить переключение контекстов в многопоточной среде.

No comments:

Post a Comment