https://compilers.ispras.ru/wiki/api.php?action=feedcontributions&user=Admin&feedformat=atomCompilers Wiki - Вклад участника [ru]2024-03-29T10:57:32ZВклад участникаMediaWiki 1.30.0https://compilers.ispras.ru/wiki/index.php?title=%D0%A1%D0%B8-%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D1%84%D0%B5%D0%B9%D1%81&diff=128Си-интерфейс2018-04-19T21:12:26Z<p>Admin: </p>
<hr />
<div>Как уже указывалось в [[FAQ]], неофициальный Cи-интерфейс [[QBE]] представлен файлом [https://c9x.me/git/?p=qbe.git;a=blob;f=all.h;h=24a175526ffea1d56d6084f24d1ef496be716dd7;hb=HEAD all.h] в корневой директории проекта.<br><br />
На данной странице мы попытались собрать основные структуры и функции, которые могут понадобится в курсе "Конструирование компиляторов".<br />
<br />
<strong>Кроме того, реализована документация в формате doxygen. Доступно по [http://83.149.198.179:9000 ссылке].<br />
<br />
[[Структура Fn |struct Fn]]<br />
[[Структура_Tmp |struct Tmp]]<br />
[[Структура_Blk |struct Blk]]<br />
[[Структура_Ins |struct Ins]]<br />
[[Структура_Ref |struct Ref]]<br />
[[Структура_Op |struct Op]]<br />
[[Структура_Use |struct Use]]<br />
[[Tmp0 |unsigned long long Tmp0]]<br />
/* parse.c */<br />
[[Массив_optab | extern Op optab[NOp]]]<br />
[[Функция_parse | void parse(FILE *, char *, void (Dat *), void (Fn *))]]<br />
[[Функция_printfn | void printfn(Fn *, FILE *)]]<br />
/* ssa.c */<br />
[[Функция_filluse | void filluse(Fn *)]]<br />
[[Функция_ssa | void ssa(Fn *)]]<br />
/* cfg.c */<br />
[[Функция_fillpreds | void fillpreds(Fn *)]]<br />
[[Функция_fillrpo | void fillrpo(Fn *)]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_parse&diff=127Функция parse2018-04-06T12:20:16Z<p>Admin: </p>
<hr />
<div>Функция <strong>parse(FILE *f, char *path, void data(Dat *), void func(Fn *))</strong> - функция, реализованная в [[ Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>parse.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Аргументы функции ==<br />
<br />
*<code>FILE *f</code> - хендл файла, откуда происходит чтение программы.<br />
*<code>char *path</code> - путь к этому файлу (используется только для сообщений об ошибках, так что неважен).<br />
*<code>void data(Dat *)</code> - функция, вызываемая для каждого распарсенного куска данных.<br />
*<code>void func(Fn *)</code> - функция, вызываемая для каждой распарсенной функции.<br />
<br />
== Назначение ==<br />
<strong>parse</strong> осуществляет парсинг [[QBE]] файла во внутреннее представление, с которым происходит взаимодействие внутри некоторой функции (внутри крутится вечный цикл со свитчами, которые еще что-то парсят). В примере считывание происходит, очевидно с <code>stdin</code>, работать с внутренним представлением функции предлагают в <code>func</code>, <code>data</code> не используется. <br />
<br />
== Исходный код ==<br />
Функция <strong>parse</strong> из <code>parse.c</code><br />
void parse(FILE *f, char *path, void data(Dat *), void func(Fn *))<br />
{<br />
int t, export;<br />
<br />
lexinit();<br />
inf = f;<br />
inpath = path;<br />
lnum = 1;<br />
thead = Txxx;<br />
ntyp = 0;<br />
typ = vnew(0, sizeof typ[0], Pheap);<br />
for (;;) {<br />
export = 0;<br />
switch (nextnl()) {<br />
default:<br />
err("top-level definition expected");<br />
case Texport:<br />
export = 1;<br />
t = nextnl();<br />
if (t == Tfunc) {<br />
case Tfunc:<br />
func(parsefn(export));<br />
break;<br />
}<br />
else if (t == Tdata) {<br />
case Tdata:<br />
parsedat(data, export);<br />
break;<br />
}<br />
else<br />
err("export can only qualify data and function");<br />
case Ttype:<br />
parsetyp();<br />
break;<br />
case Teof:<br />
vfree(typ);<br />
return;<br />
}<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_printfn&diff=126Функция printfn2018-04-06T12:17:09Z<p>Admin: Новая страница: «Функция <strong>printfn(Fn *fn, FILE *f)</strong> - функция, реализованная в Си интерфейсе…»</p>
<hr />
<div>Функция <strong>printfn(Fn *fn, FILE *f)</strong> - функция, реализованная в [[ Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>parse.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>printfn</strong> осуществляет печать функции <code>fn</code> в виде кода на [[QBE]].<br />
<br />
== Исходный код ==<br />
Функция <strong>printfn</strong> из <code>parse.c</code><br />
void printfn(Fn *fn, FILE *f)<br />
{<br />
static char ktoc[] = "wlsd";<br />
static char *jtoa[NJmp] = {<br />
#define X(j) [J##j] = #j,<br />
JMPS(X)<br />
#undef X<br />
};<br />
Blk *b;<br />
Phi *p;<br />
Ins *i;<br />
uint n;<br />
<br />
if (fn->export)<br />
fprintf(f, "export ");<br />
fprintf(f, "function $%s() {\n", fn->name);<br />
for (b=fn->start; b; b=b->link) {<br />
fprintf(f, "@%s\n", b->name);<br />
for (p=b->phi; p; p=p->link) {<br />
fprintf(f, "\t");<br />
printref(p->to, fn, f);<br />
fprintf(f, " =%c phi ", ktoc[p->cls]);<br />
assert(p->narg);<br />
for (n=0;; n++) {<br />
fprintf(f, "@%s ", p->blk[n]->name);<br />
printref(p->arg[n], fn, f);<br />
if (n == p->narg-1) {<br />
fprintf(f, "\n");<br />
break;<br />
} else<br />
fprintf(f, ", ");<br />
}<br />
}<br />
for (i=b->ins; i-b->ins < b->nins; i++) {<br />
fprintf(f, "\t");<br />
if (!req(i->to, R)) {<br />
printref(i->to, fn, f);<br />
fprintf(f, " =%c ", ktoc[i->cls]);<br />
}<br />
assert(optab[i->op].name);<br />
fprintf(f, "%s", optab[i->op].name);<br />
if (req(i->to, R))<br />
switch (i->op) {<br />
case Oarg:<br />
case Oswap:<br />
case Oxcmp:<br />
case Oacmp:<br />
case Oacmn:<br />
case Oafcmp:<br />
case Oxtest:<br />
case Oxdiv:<br />
case Oxidiv:<br />
fputc(ktoc[i->cls], f);<br />
}<br />
if (!req(i->arg[0], R)) {<br />
fprintf(f, " ");<br />
printref(i->arg[0], fn, f);<br />
}<br />
if (!req(i->arg[1], R)) {<br />
fprintf(f, ", ");<br />
printref(i->arg[1], fn, f);<br />
}<br />
fprintf(f, "\n");<br />
}<br />
switch (b->jmp.type) {<br />
case Jret0:<br />
case Jretw:<br />
case Jretl:<br />
case Jrets:<br />
case Jretd:<br />
case Jretc:<br />
fprintf(f, "\t%s", jtoa[b->jmp.type]);<br />
if (b->jmp.type != Jret0 || !req(b->jmp.arg, R)) {<br />
fprintf(f, " ");<br />
printref(b->jmp.arg, fn, f);<br />
}<br />
if (b->jmp.type == Jretc)<br />
fprintf(f, ", :%s", typ[fn->retty].name);<br />
fprintf(f, "\n");<br />
break;<br />
case Jjmp:<br />
if (b->s1 != b->link)<br />
fprintf(f, "\tjmp @%s\n", b->s1->name);<br />
break;<br />
default:<br />
fprintf(f, "\t%s ", jtoa[b->jmp.type]);<br />
if (b->jmp.type == Jjnz) {<br />
printref(b->jmp.arg, fn, f);<br />
fprintf(f, ", ");<br />
}<br />
fprintf(f, "@%s, @%s\n", b->s1->name, b->s2->name);<br />
break;<br />
}<br />
}<br />
fprintf(f, "}\n");<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_fillrpo&diff=125Функция fillrpo2018-04-06T12:10:15Z<p>Admin: </p>
<hr />
<div>Функция <strong>fillrpo(Fn)</strong> - функция, реализованная в [[Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>cfg.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>fillrpo</strong> осуществляет обход дерева [[Структура Blk | блоков]] в reverse postorder порядке. Вычисленные номера [[Структура Blk | блоков]] записываются в <code>blk->id</code>.<br />
<br />
== Исходный код ==<br />
Функция <strong>fillrpo</strong> из <code>cfg.c</code><br />
void fillrpo(Fn *f) {<br />
uint n;<br />
Blk *b, **p;<br />
for (b=f->start; b; b=b->link)<br />
b->id = -1u;<br />
n = 1 + rporec(f->start, f->nblk-1);<br />
f->nblk -= n;<br />
f->rpo = alloc(f->nblk * sizeof f->rpo[0]);<br />
for (p=&f->start; (b=*p);) {<br />
if (b->id == -1u) {<br />
edgedel(b, &b->s1);<br />
edgedel(b, &b->s2);<br />
*p = b->link;<br />
} else {<br />
b->id -= n;<br />
f->rpo[b->id] = b;<br />
p = &b->link;<br />
}<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_fillpreds&diff=124Функция fillpreds2018-04-06T12:09:49Z<p>Admin: </p>
<hr />
<div>Функция <strong>fillpreds(Fn)</strong> - функция, реализованная в [[Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>cfg.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>fillpreds</strong> осуществляет заполнение полей <code>pred</code>, <code>npred</code>, <code>visit</code> во всех [[Структура Blk | блоках]] функции.<br />
<br />
== Исходный код ==<br />
Функция <strong>fillpreds</strong> из <code>cfg.c</code><br />
/* fill predecessors information in blocks */<br />
void fillpreds(Fn *f) {<br />
Blk *b;<br />
for (b=f->start; b; b=b->link) {<br />
b->npred = 0;<br />
b->pred = 0;<br />
}<br />
for (b=f->start; b; b=b->link) {<br />
if (b->s1)<br />
b->s1->npred++;<br />
if (b->s2 && b->s2 != b->s1)<br />
b->s2->npred++;<br />
}<br />
for (b=f->start; b; b=b->link) {<br />
if (b->s1)<br />
addpred(b, b->s1);<br />
if (b->s2 && b->s2 != b->s1)<br />
addpred(b, b->s2);<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_filluse&diff=123Функция filluse2018-04-06T12:09:29Z<p>Admin: </p>
<hr />
<div>Функция <strong>filluse(Fn)</strong> - функция, реализованная в [[ Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>ssa.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>filluse</strong> осуществляет заполнение структур <code>fn->tmp</code> для <code>fn</code> и структур <code>tmp.use</code> для всех <code>fn->tmp</code>.<br />
<br />
== Исходный код ==<br />
Функция <strong>filluse</strong> из <code>ssa.c</code><br />
/* fill predecessors information in blocks */<br />
/* fill usage, width, phi, and class information<br />
* must not change .visit fields */<br />
void filluse(Fn *fn) {<br />
Blk *b;<br />
Phi *p;<br />
Ins *i;<br />
int m, t, tp, w;<br />
uint a;<br />
Tmp *tmp;<br />
/* todo, is this the correct file? */<br />
tmp = fn->tmp;<br />
for (t=Tmp0; t<fn->ntmp; t++) {<br />
tmp[t].ndef = 0;<br />
tmp[t].nuse = 0;<br />
tmp[t].cls = 0;<br />
tmp[t].phi = 0;<br />
tmp[t].width = WFull;<br />
if (tmp[t].use == 0)<br />
tmp[t].use = vnew(0, sizeof(Use), Pfn);<br />
}<br />
for (b=fn->start; b; b=b->link) {<br />
for (p=b->phi; p; p=p->link) {<br />
assert(rtype(p->to) == RTmp);<br />
tp = p->to.val;<br />
tmp[tp].ndef++;<br />
tmp[tp].cls = p->cls;<br />
tp = phicls(tp, fn->tmp);<br />
for (a=0; a<p->narg; a++)<br />
if (rtype(p->arg[a]) == RTmp) {<br />
t = p->arg[a].val;<br />
adduse(&tmp[t], UPhi, b, p);<br />
t = phicls(t, fn->tmp);<br />
if (t != tp)<br />
tmp[t].phi = tp;<br />
}<br />
}<br />
for (i=b->ins; i-b->ins < b->nins; i++) {<br />
if (!req(i->to, R)) {<br />
assert(rtype(i->to) == RTmp);<br />
w = WFull;<br />
if (isload(i->op) && i->op != Oload)<br />
w = Wsb + (i->op - Oloadsb);<br />
if (isext(i->op))<br />
w = Wsb + (i->op - Oextsb);<br />
if (w == Wsw || w == Wuw)<br />
if (i->cls == Kw)<br />
w = WFull;<br />
t = i->to.val;<br />
tmp[t].width = w;<br />
tmp[t].ndef++;<br />
tmp[t].cls = i->cls;<br />
}<br />
for (m=0; m<2; m++)<br />
if (rtype(i->arg[m]) == RTmp) {<br />
t = i->arg[m].val;<br />
adduse(&tmp[t], UIns, b, i);<br />
}<br />
}<br />
if (rtype(b->jmp.arg) == RTmp)<br />
adduse(&tmp[b->jmp.arg.val], UJmp, b);<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_ssa&diff=122Функция ssa2018-04-06T12:08:58Z<p>Admin: </p>
<hr />
<div>Функция <strong>ssa(Fn)</strong> - функция, реализованная в [[Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>cfg.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>ssa</strong> осуществляет построение [https://ru.wikipedia.org/wiki/SSA SSA-формы]. <br />
#Заполняет dominance frontier (границы доминирования), кладет в <code>blk->fron</code> (размер множества - в <code>blk->nfron</code>); <br />
#Заполняет живые переменные; <br />
#Строит [https://ru.wikipedia.org/wiki/SSA SSA-форму], меняя fn.<br />
<br />
== Исходный код ==<br />
Функция <strong>ssa</strong> из <code>ssa.c</code><br />
/* require rpo and ndef */<br />
void ssa(Fn *fn) {<br />
Name **stk, *n;<br />
int d, nt;<br />
Blk *b, *b1;<br />
nt = fn->ntmp;<br />
stk = emalloc(nt * sizeof stk[0]);<br />
d = debug['L'];<br />
debug['L'] = 0;<br />
filldom(fn);<br />
if (debug['N']) {<br />
fprintf(stderr, "\n> Dominators:\n");<br />
for (b1=fn->start; b1; b1=b1->link) {<br />
if (!b1->dom)<br />
continue;<br />
fprintf(stderr, "%10s:", b1->name);<br />
for (b=b1->dom; b; b=b->dlink)<br />
fprintf(stderr, " %s", b->name);<br />
fprintf(stderr, "\n");<br />
}<br />
}<br />
fillfron(fn);<br />
filllive(fn);<br />
phiins(fn);<br />
renblk(fn->start, stk, fn);<br />
while (nt--)<br />
while ((n=stk[nt])) {<br />
stk[nt] = n->up;<br />
nfree(n);<br />
}<br />
debug['L'] = d;<br />
free(stk);<br />
if (debug['N']) {<br />
fprintf(stderr, "\n> After SSA construction:\n");<br />
printfn(fn, stderr);<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_parse&diff=121Функция parse2018-04-06T12:08:20Z<p>Admin: </p>
<hr />
<div>Функция <strong>parse(FILE *f, char *path, void data(Dat *), void func(Fn *))</strong> - функция, реализованная в [[ Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>parse.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>parse</strong> осуществляет парсинг [[QBE]] файла во внутреннее представление, с которым происходит взаимодействие внутри некоторой функции (внутри крутится вечный цикл со свитчами, которые еще что-то парсят). В примере считывание происходит, очевидно с <code>stdin</code>, работать с внутренним представлением функции предлагают в <code>func</code>, <code>data</code> не используется. <br />
<br />
== Исходный код ==<br />
Функция <strong>parse</strong> из <code>parse.c</code><br />
void parse(FILE *f, char *path, void data(Dat *), void func(Fn *))<br />
{<br />
int t, export;<br />
<br />
lexinit();<br />
inf = f;<br />
inpath = path;<br />
lnum = 1;<br />
thead = Txxx;<br />
ntyp = 0;<br />
typ = vnew(0, sizeof typ[0], Pheap);<br />
for (;;) {<br />
export = 0;<br />
switch (nextnl()) {<br />
default:<br />
err("top-level definition expected");<br />
case Texport:<br />
export = 1;<br />
t = nextnl();<br />
if (t == Tfunc) {<br />
case Tfunc:<br />
func(parsefn(export));<br />
break;<br />
}<br />
else if (t == Tdata) {<br />
case Tdata:<br />
parsedat(data, export);<br />
break;<br />
}<br />
else<br />
err("export can only qualify data and function");<br />
case Ttype:<br />
parsetyp();<br />
break;<br />
case Teof:<br />
vfree(typ);<br />
return;<br />
}<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_parse&diff=120Функция parse2018-04-06T12:07:56Z<p>Admin: Новая страница: «Функция <strong>parse(FILE *f, char *path, void data(Dat *), void func(Fn *))</strong> - функция, реализованная в Си-интерф…»</p>
<hr />
<div>Функция <strong>parse(FILE *f, char *path, void data(Dat *), void func(Fn *))</strong> - функция, реализованная в [[ Си-интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>parse.c</code> и "подключается" в <code>[[ Си-интерфейс | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>parse</strong> осуществляет парсинг [[QBE]] файла во внутреннее представление, с которым происходит взаимодействие внутри некоторой функции (внутри крутится вечный цикл со свитчами, которые еще что-то парсят). В примере считывание происходит, очевидно с <code>stdin</code>, работать с внутренним представлением функции предлагают в <code>func</code>, <code>data</code> не используется. <br />
<br />
== Исходный код ==<br />
Функция <strong>parse</strong> из <code>parse.c</code><br />
void parse(FILE *f, char *path, void data(Dat *), void func(Fn *))<br />
{<br />
int t, export;<br />
<br />
lexinit();<br />
inf = f;<br />
inpath = path;<br />
lnum = 1;<br />
thead = Txxx;<br />
ntyp = 0;<br />
typ = vnew(0, sizeof typ[0], Pheap);<br />
for (;;) {<br />
export = 0;<br />
switch (nextnl()) {<br />
default:<br />
err("top-level definition expected");<br />
case Texport:<br />
export = 1;<br />
t = nextnl();<br />
if (t == Tfunc) {<br />
case Tfunc:<br />
func(parsefn(export));<br />
break;<br />
}<br />
else if (t == Tdata) {<br />
case Tdata:<br />
parsedat(data, export);<br />
break;<br />
}<br />
else<br />
err("export can only qualify data and function");<br />
case Ttype:<br />
parsetyp();<br />
break;<br />
case Teof:<br />
vfree(typ);<br />
return;<br />
}<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%81%D0%B8%D0%B2_optab&diff=119Массив optab2018-04-06T11:57:51Z<p>Admin: Новая страница: «Массив <strong>optab</strong> – массив, содержащий таблицу всех операций языка QBE IL, обращаясь…»</p>
<hr />
<div>Массив <strong>optab</strong> – массив, содержащий таблицу всех операций языка [[QBE|QBE IL]], обращаясь к i-ому элементу этого массива, мы обратимся к i-ой операции этого языка (очевидно, число i обычно заранее задается парсером).</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A1%D0%B8-%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D1%84%D0%B5%D0%B9%D1%81&diff=118Си-интерфейс2018-04-06T11:55:43Z<p>Admin: </p>
<hr />
<div>Как уже указывалось в [[FAQ]], неофициальный Cи-интерфейс [[QBE]] представлен файлом [https://c9x.me/git/?p=qbe.git;a=blob;f=all.h;h=24a175526ffea1d56d6084f24d1ef496be716dd7;hb=HEAD all.h] в корневой директории проекта.<br><br />
На данной странице мы попытались собрать основные структуры и функции, которые могут понадобится в курсе "Конструирование компиляторов".<br />
<br />
[[Структура Fn |struct Fn]]<br />
[[Структура_Tmp |struct Tmp]]<br />
[[Структура_Blk |struct Blk]]<br />
[[Структура_Ins |struct Ins]]<br />
[[Структура_Ref |struct Ref]]<br />
[[Структура_Op |struct Op]]<br />
[[Структура_Use |struct Use]]<br />
[[Tmp0 |unsigned long long Tmp0]]<br />
/* parse.c */<br />
[[Массив_optab | extern Op optab[NOp]]]<br />
[[Функция_parse | void parse(FILE *, char *, void (Dat *), void (Fn *))]]<br />
[[Функция_printfn | void printfn(Fn *, FILE *)]]<br />
/* ssa.c */<br />
[[Функция_filluse | void filluse(Fn *)]]<br />
[[Функция_ssa | void ssa(Fn *)]]<br />
/* cfg.c */<br />
[[Функция_fillpreds | void fillpreds(Fn *)]]<br />
[[Функция_fillrpo | void fillrpo(Fn *)]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A1%D0%B8-%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D1%84%D0%B5%D0%B9%D1%81&diff=117Си-интерфейс2018-04-06T11:52:57Z<p>Admin: </p>
<hr />
<div>Как уже указывалось в [[FAQ]], неофициальный Cи-интерфейс [[QBE]] представлен файлом [https://c9x.me/git/?p=qbe.git;a=blob;f=all.h;h=24a175526ffea1d56d6084f24d1ef496be716dd7;hb=HEAD all.h] в корневой директории проекта.<br><br />
На данной странице мы попытались собрать основные структуры и функции, которые могут понадобится в курсе "Конструирование компиляторов".<br />
<br />
[[Структура Fn | struct Fn]]<br />
[[Структура_Tmp | struct Tmp]]<br />
[[Структура_Blk | struct Blk]]<br />
[[Структура_Ins | struct Ins]]<br />
[[Структура_Ref | struct Ref]]<br />
[[Структура_Op | struct Op]]<br />
[[Структура_Use | struct Use]]<br />
[[Tmp0]]<br />
/* parse.c */<br />
[[Массив_optab | extern Op optab[NOp]]]<br />
[[Функция_parse | void parse(FILE *, char *, void (Dat *), void (Fn *))]]<br />
[[Функция_printfn | void printfn(Fn *, FILE *)]]<br />
/* ssa.c */<br />
[[Функция_filluse | void filluse(Fn *)]]<br />
[[Функция_ssa | void ssa(Fn *)]]<br />
/* cfg.c */<br />
[[Функция_fillpreds | void fillpreds(Fn *)]]<br />
[[Функция_fillrpo | void fillrpo(Fn *)]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%D0%BC&diff=116Теория к заданиям2018-04-05T15:23:41Z<p>Admin: </p>
<hr />
<div>== Множества Gen и Kill ==<br />
<br />
В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output).<br />
*gen – множество определений, порождаемых инструкцией<br />
*kill – множество определений, убиваемых инструкцией<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:<br />
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;<br />
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.<br />
<br />
== Достигающие определения ==<br />
<br />
Из лекций:<br />
*<strong>Определением переменной x</strong> называется инструкция, которая<br />
присваивает значение переменной <code>х</code>.<br />
*<strong>Использованием переменной x</strong> является инструкция, одним из<br />
операндов которой является переменная <code>х</code>.<br />
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее<br />
определение.<br />
*Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым.<br />
<br />
<div style="float:right;">[[File:RDexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
Начало блока B2 достигается определениями:<br />
*(i, B1), (j, B1), (a, B1),<br />
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)<br />
*(a, B3)<br />
*(i, B4)<br />
<br />
(i, B2) не достигает начала B2, так как его убивает (i, B4)<br />
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> <br />
Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia].<br />
<br />
== Множества Def и Use ==<br />
<br />
*def – множество переменных, определяемых в блоке В до их использования в этом блоке (любая переменная из defB мертва на входе в блок В).<br />
*use – множество переменных, используемых в блоке В до их определения в этом блоке (любая переменная из useB жива на входе в блок В).<br />
<br />
<div style="float:right;">[[File:DUexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
*в блоке B2 переменные i и j используются до их переопределения, следовательно,<br />
useB2 = {(i,B1), (i,B4), (j,B1)} = (1100001)<br />
<br />
*в блоке B2 определяются новые значения переменных i и j, так что<br />
defB2 = {(i,B2), (j,B2)} = (0001100)<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Пример алгоритма и дополнительную информацию можно найти на [https://github.com/wisestump/OptimizingCompiler/blob/4105258f3865a6ebed70a1445fbf1f1df264a61c/documentation/PiedPiper/PiedPiper-DefUseCalculation.md github]. <br />
<u>Обратите внимание</u>, в примерах следующего вида:<br />
export function w $f(w %n, w %m) {<br />
@start<br />
%a =w add 1, 1<br />
@end<br />
ret %a<br />
}<br />
переменная <code>%a</code> должна входить в <code>use(ret)</code>.<br />
<br />
== Живые переменные ==<br />
<br />
Для определения переменной x в точке p программы выяснить, будет ли указанное значение x использоваться вдоль какого-нибудь пути, начинающемся в точке p.<br />
*Если да – переменная x жива (активна) в точке p.<br />
*Если нет – переменная x мертва (неактивна) в точке p.<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Фактически, это Reaching Definitions (Достигающие определения) наоборот. <br />
Пример алгоритма.<br />
for (каждый базовый блок B) {<br />
In[B] = ∅<br />
}<br />
while (внесены изменения в In) {<br />
for (каждый базовый блок, отличный от выходного) {<br />
Out[B] = ⋃In[S], S - преемник В<br />
In[B] = use[B] ∪ (Out[B] \ def[B])<br />
}<br />
}<br />
Тогда живые переменные блока - это его Out.<br />
<br />
== Доминаторы ==<br />
Из лекций:<br />
В [https://ru.wikipedia.org/wiki/Граф_потока_управления ГПУ] вершина <code>d</code> является <strong>доминатором</strong> вершины <code>n</code> (этот факт записывается как <code>d dom n</code> или <code>d = Dom(n))</code>, если любой путь от вершины <code>Entry</code> до вершины <code>n</code> проходит через вершину <code>d</code>.<br />
<br />
Другой вариант определения. <br />
Узел <code>d</code> графа потока доминирует над узлом <code>n</code>, если любой путь от входного узла графа потока к <code>n</code> проходит через <code>d</code>. Заметим, что при таком определении каждый узел доминирует над самим собой.<br />
<br />
== Форма SSA ==<br />
Из лекций:<br />
Форма статического единственного присваивания (SSA) позволяет в каждой точке программы объединить<br />
*информацию об имени переменной<br />
*с информацией о текущем значении этой переменной (или, что то же самое, с информацией о том, какое из определений данной переменной определяет ее текущее значение в данной точке).<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> Вы также можете почерпнуть некоторую дополнительную информацию в соответствующей статье на [https://ru.wikipedia.org/wiki/SSA Wikipedia].<br />
<br />
== Граница доминирования ==<br />
Из лекций:<br />
Границей доминирования n, DF(n), называется множество узлов m, удоволетворяющих условиям:<br />
# n является доминатором предшественника m<br />
#: <code>p &isin; Pred(m) & n &isin; Dom(p)</code><br />
# n не является строгим доминатором m<br />
#: <code>n &notin; (Dom (m) – {m})</code><br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
<br />
== Бесполезный код ==</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=115Заглавная страница2018-04-05T13:38:00Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Тем, кто продолжит поддерживать и развивать данный проект, рекомендуется ознакомиться со статьей [[Оформление]].<br />
<br />
== Навигация ==<br />
<br />
# Страница [[QBE]] содержит общее описание языка. Ниже, на данной странице, приводится навигация по переведенной оригинальной документации;<br><br />
# Страница [[Си-интерфейс]] является "входной" к страницам с описанием и разбором некоторого содержимого его файлов;<br><br />
# Страница [[Примеры кода QBE IL]] содержит небольшую инструкцию по эксплуатации языка [[QBE]];<br><br />
# Страница [[FAQ]] ответит на распространенные вопросы, которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Страница [[Теория к заданиям]] разъясняет некоторые термины, с которыми Вы столкнетесь в курсе "Конструирование компиляторов".<br />
<br />
== Документация QBE ==<br />
Оригинальная документация расположена на сайте [http://c9x.me/compile/ c9x.me].<br />
Перевод оригинальной документации на Wiki:<br />
<br />
# [[QBE]]<br />
# Типы<br />
## [[Простые типы данных]]<br />
## [[Подтипы | Подтипирование]]<br />
# [[Константы]]<br />
# [[Объявления]]<br />
## [[Составные типы данных]]<br />
## [[Data]]<br />
## [[Функции]]<br />
# Управление<br />
## [[Блоки]]<br />
## [[Переходы]]<br />
# [[Инструкции]]<br />
## [[Арифметические и битовые операции]]<br />
## [[Память]]<br />
## [[Сравнения]]<br />
## [[Преобразования]]<br />
## [[Инструкции Cast и Copy]]<br />
## [[Инструкция Call]]<br />
## [[Вариативность]]<br />
## [[Инструкция Phi]]<br />
# [[Инструкции QBE | Список всех инструкций]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9E%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5&diff=114Оформление2018-04-05T13:36:30Z<p>Admin: </p>
<hr />
<div>Для тех, кто будет в дальнейшем заниматься наполнением данной Wiki, предлагается ознакомиться с общими для всех подобных статей и вещей и использовать следующую структуру.<br />
<br />
# Каждый текст разбивается на визуально удобно читабельные абзацы.<br />
##Если у текста есть первоисточник, то под каждым таким абзацем указывать аналогичный абзац первоисточника.<br />
###Думаю, теги <code>pre</code> для выделения оригинала подойдут.<br />
###Для каждой статьи обязательно указывать ресурс-первоисточник. Это можно сделать единоразово, в конце страницы: два отступа («\n») от конца текста, разделительная черта (<code>h1</code>, но лучше 4 тире - черта в Wiki-разметке), текст «Источник: », домен, к которому прилагается точная ссылка. Пример. Источник: [https://c9x.me/compile/doc/il.html#Types c9x.me].<br />
##Разрешается создавать Wiki-структуры и использовать возможности HTML для оформления страниц.<br />
#В каждой статье, в случае, если применяются аббревиатуры, либо термины, к каждому такому термину в русскоязычном тексте/переводе указывать ссылку на сторонний ресурс ([ссылка Термин]) или на уже существующую на нашей Wiki статью (<pre>[[Термин]]</pre> или, если термин склоняется, <pre>[[СтатьяНаWiki | Термин]]</pre>).<br />
#Код оформляется двумя способами.<br />
##Если строка используется в где-то в тексте, то её нужно выделить либо тегами <pre><code></code></pre>, либо <pre><b></b></pre> = <pre><strong></strong></pre><br />
##Если код приводится после текста/абзаца, то каждая строка к каждой строке с кодом добавляем пробел в ее начало. Это выделит код в блок.<br />
###Если в тексте есть указание на какой-то конкретный пример кода, который уже был приведен, либо только будет приведен, желательно, первую строку в п. 3.2. начать с <pre><strong>Пример.<strong></pre><br />
###Если в тексте присутствует не один пример, а несколько, то каждый блок кода, являющийся примером, должен начинаться с <pre><strong>Пример НомерПримера.</strong></pre><br />
##Комментарии в блоках кода для удобства чтения будем указывать по принципу QBE (у Python так же) - через символ решетки. То есть, например, </code>%a = w add 0,1 # Кладем 1 в переменную а</code>.<br />
#В массивных текстах, в которых возможно логическое разделение на главы, лучше это практиковать. В Wiki-разметке первый уровень выделяется в два знака равно, второй в три знака равно, третий - в четыре, и тд. Пример: <pre>== Глава 1 ==, === Раздел 1 (первой главы) ===</pre><br />
#В случае возникновения проблем с переводом, либо при отсутствии возможности однозначной трактовки, обязательно указывать через слэш, либо в круглых скобках вторую возможную трактовку/комментарий/примечание.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9E%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5&diff=113Оформление2018-04-05T13:36:08Z<p>Admin: </p>
<hr />
<div>Для тех, кто будет в дальнейшем заниматься наполнением данной Wiki, предлагается ознакомиться с общими для всех подобных статей и вещей и использовать следующую структуру.<br />
<br />
# Каждый текст разбивается на визуально удобно читабельные абзацы.<br />
##Если у текста есть первоисточник, то под каждым таким абзацем указывать аналогичный абзац первоисточника.<br />
###Думаю, теги <code>pre</code> для выделения оригинала подойдут.<br />
###Для каждой статьи обязательно указывать ресурс-первоисточник. Это можно сделать единоразово, в конце страницы: два отступа («\n») от конца текста, разделительная черта (<code>h1</code>, но лучше 4 тире - черта в Wiki-разметке), текст «Источник: », домен, к которому прилагается точная ссылка. Пример. Источник: [https://c9x.me/compile/doc/il.html#Types c9x.me].<br />
##Разрешается создавать Wiki-структуры и использовать возможности HTML для оформления страниц.<br />
#В каждой статье, в случае, если применяются аббревиатуры, либо термины, к каждому такому термину в русскоязычном тексте/переводе указывать ссылку на сторонний ресурс ([ссылка Термин]) или на уже существующую на нашей Wiki статью (<pre>[[Термин]]</pre> или, если термин склоняется, <pre>[[СтатьяНаWiki | Термин]]</pre>).<br />
#Код оформляется двумя способами.<br />
##Если строка используется в где-то в тексте, то её нужно выделить либо тегами <pre><code></code></pre>, либо <pre><b></b></pre> = <pre><strong></strong></pre><br />
##Если код приводится после текста/абзаца, то каждая строка к каждой строке с кодом добавляем пробел в ее начало. Это выделит код в блок.<br />
###Если в тексте есть указание на какой-то конкретный пример кода, который уже был приведен, либо только будет приведен, желательно, первую строку в п. 3.2. начать с <pre><strong>Пример.<strong></pre><br />
###Если в тексте присутствует не один пример, а несколько, то каждый блок кода, являющийся примером, должен начинаться с <pre><strong>Пример НомерПримера.</strong></pre><br />
##Комментарии в блоках кода для удобства чтения будем указывать по принципу QBE (у Python так же) - через символ решетки. То есть, например, </code>%a = w add 0,1 # Кладем 1 в переменную а</code.<br />
#В массивных текстах, в которых возможно логическое разделение на главы, лучше это практиковать. В Wiki-разметке первый уровень выделяется в два знака равно, второй в три знака равно, третий - в четыре, и тд. Пример: <pre>== Глава 1 ==, === Раздел 1 (первой главы) ===</pre>.<br />
#В случае возникновения проблем с переводом, либо при отсутствии возможности однозначной трактовки, обязательно указывать через слэш, либо в круглых скобках вторую возможную трактовку/комментарий/примечание.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9E%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5&diff=112Оформление2018-04-05T13:30:27Z<p>Admin: Новая страница: «Для тех, кто будет в дальнейшем заниматься наполнением данной Wiki, предлагается ознакоми…»</p>
<hr />
<div>Для тех, кто будет в дальнейшем заниматься наполнением данной Wiki, предлагается ознакомиться с общими для всех подобных статей и вещей и использовать следующую структуру.<br />
<br />
# Каждый текст разбивается на визуально удобно читабельные абзацы.<br />
##Если у текста есть первоисточник, то под каждым таким абзацем указывать аналогичный абзац первоисточника.<br />
###Думаю, теги <pre></pre> для выделения оригинала подойдут.<br />
###Для каждой статьи обязательно указывать ресурс-первоисточник. Это можно сделать единоразово, в конце страницы: два отступа («\n») от конца текста, разделительная черта (<h1>, но лучше 4 тире - черта в Wiki-разметке), текст «Источник: », домен, к которому прилагается точная ссылка. Пример. Источник: [https://c9x.me/compile/doc/il.html#Types c9x.me].<br />
##Разрешается создавать Wiki-структуры и использовать возможности HTML для оформления страниц.<br />
#В каждой статье, в случае, если применяются аббревиатуры, либо термины, к каждому такому термину в русскоязычном тексте/переводе указывать ссылку на сторонний ресурс ([ссылка Термин]) или на уже существующую на нашей Wiki статью ([[Термин]] или, если термин склоняется, [[СтатьяНаWiki | Термин]]).<br />
#Код оформляется двумя способами.<br />
##Если строка используется в где-то в тексте, то её нужно выделить либо тегами <code></code>, либо <b></b> = <strong></strong>.<br />
##Если код приводится после текста/абзаца, то каждая строка к каждой строке с кодом добавляем пробел в ее начало. Это выделит код в блок.<br />
###Если в тексте есть указание на какой-то конкретный пример кода, который уже был приведен, либо только будет приведен, желательно, первую строку в п. 3.2. начать с <strong>Пример.<strong>.<br />
###Если в тексте присутствует не один пример, а несколько, то каждый блок кода, являющийся примером, должен начинаться с <strong>Пример НомерПримера.</strong>.<br />
##Комментарии в блоках кода для удобства чтения будем указывать по принципу QBE (у Python так же) - через символ решетки. То есть, например, %a = w add 0,1 # Кладем 1 в переменную а.<br />
#В массивных текстах, в которых возможно логическое разделение на главы, лучше это практиковать. В Wiki-разметке первый уровень выделяется в два знака равно, второй в три знака равно, третий - в четыре, и тд. Пример: == Глава 1 ==, === Раздел 1 (первой главы) ===.<br />
#В случае возникновения проблем с переводом, либо при отсутствии возможности однозначной трактовки, обязательно указывать через слэш, либо в круглых скобках вторую возможную трактовку/комментарий/примечание.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=111Заглавная страница2018-04-05T12:54:09Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
== Навигация ==<br />
<br />
# Страница [[QBE]] содержит общее описание языка. Ниже, на данной странице, приводится навигация по переведенной оригинальной документации;<br><br />
# Страница [[Си-интерфейс]] является "входной" к страницам с описанием и разбором некоторого содержимого его файлов;<br><br />
# Страница [[Примеры кода QBE IL]] содержит небольшую инструкцию по эксплуатации языка [[QBE]];<br><br />
# Страница [[FAQ]] ответит на распространенные вопросы, которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Страница [[Теория к заданиям]] разъясняет некоторые термины, с которыми Вы столкнетесь в курсе "Конструирование компиляторов".<br />
<br />
== Документация QBE ==<br />
Оригинальная документация расположена на сайте [http://c9x.me/compile/ c9x.me].<br />
Перевод оригинальной документации на Wiki:<br />
<br />
# [[QBE]]<br />
# Типы<br />
## [[Простые типы данных]]<br />
## [[Подтипы | Подтипирование]]<br />
# [[Константы]]<br />
# [[Объявления]]<br />
## [[Составные типы данных]]<br />
## [[Data]]<br />
## [[Функции]]<br />
# Управление<br />
## [[Блоки]]<br />
## [[Переходы]]<br />
# [[Инструкции]]<br />
## [[Арифметические и битовые операции]]<br />
## [[Память]]<br />
## [[Сравнения]]<br />
## [[Преобразования]]<br />
## [[Инструкции Cast и Copy]]<br />
## [[Инструкция Call]]<br />
## [[Вариативность]]<br />
## [[Инструкция Phi]]<br />
# [[Инструкции QBE | Список всех инструкций]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A1%D0%B8-%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D1%84%D0%B5%D0%B9%D1%81&diff=110Си-интерфейс2018-04-05T12:38:40Z<p>Admin: </p>
<hr />
<div>Как уже указывалось в [[FAQ]], неофициальный Cи-интерфейс [[QBE]] представлен файлом [https://c9x.me/git/?p=qbe.git;a=blob;f=all.h;h=24a175526ffea1d56d6084f24d1ef496be716dd7;hb=HEAD all.h] в корневой директории проекта.<br><br />
На данной странице мы попытались собрать основные структуры и функции, которые могут понадобится в курсе "Конструирование компиляторов".<br />
<br />
[[Структура Fn | struct Fn]]<br />
[[Структура_Tmp | struct Tmp]]<br />
[[Структура_Blk | struct Blk]]<br />
[[Структура_Ins | struct Ins]]<br />
[[Структура_Ref | struct Ref]]<br />
[[Структура_Op | struct Op]]<br />
[[Структура_Use | struct Use]]<br />
[[Tmp0]]<br />
/* ssa.c */<br />
[[Функция_filluse | void filluse(Fn *)]]<br />
[[Функция_ssa | void ssa(Fn *)]]<br />
/* cfg.c */<br />
[[Функция_fillpreds | void fillpreds(Fn *)]]<br />
[[Функция_fillrpo | void fillrpo(Fn *)]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A1%D0%B8-%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D1%84%D0%B5%D0%B9%D1%81&diff=109Си-интерфейс2018-04-05T12:38:14Z<p>Admin: Новая страница: «Как уже указывалось в FAQ, неофициальный Cи-интерфейс QBE представлен файлом [https://c9x.me/git…»</p>
<hr />
<div>Как уже указывалось в [[FAQ]], неофициальный Cи-интерфейс [[QBE]] представлен файлом [https://c9x.me/git/?p=qbe.git;a=blob;f=all.h;h=24a175526ffea1d56d6084f24d1ef496be716dd7;hb=HEAD all.h] в корневой директории проекта.<br />
На данной странице мы попытались собрать основные структуры и функции, которые могут понадобится в курсе "Конструирование компиляторов".<br />
<br />
[[Структура Fn | struct Fn]]<br />
[[Структура_Tmp | struct Tmp]]<br />
[[Структура_Blk | struct Blk]]<br />
[[Структура_Ins | struct Ins]]<br />
[[Структура_Ref | struct Ref]]<br />
[[Структура_Op | struct Op]]<br />
[[Структура_Use | struct Use]]<br />
[[Tmp0]]<br />
/* ssa.c */<br />
[[Функция_filluse | void filluse(Fn *)]]<br />
[[Функция_ssa | void ssa(Fn *)]]<br />
/* cfg.c */<br />
[[Функция_fillpreds | void fillpreds(Fn *)]]<br />
[[Функция_fillrpo | void fillrpo(Fn *)]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_ssa&diff=107Функция ssa2018-04-03T21:51:21Z<p>Admin: /* Назначение */</p>
<hr />
<div>Функция <strong>ssa(Fn)</strong> - функция, реализованная в [[Си интерфейс | Си интерфейсе]] [[QBE]]. Располагается в файле <code>cfg.c</code> и "подключается" в <code>[[ all.h | all.h]]</code>.<br />
<br />
== Назначение ==<br />
<strong>ssa</strong> осуществляет построение [https://ru.wikipedia.org/wiki/SSA SSA-формы]. <br />
#Заполняет dominance frontier (границы доминирования), кладет в <code>blk->fron</code> (размер множества - в <code>blk->nfron</code>); <br />
#Заполняет живые переменные; <br />
#Строит [https://ru.wikipedia.org/wiki/SSA SSA-форму], меняя fn.<br />
<br />
== Исходный код ==<br />
Функция <strong>ssa</strong> из <code>ssa.c</code><br />
/* require rpo and ndef */<br />
void ssa(Fn *fn) {<br />
Name **stk, *n;<br />
int d, nt;<br />
Blk *b, *b1;<br />
nt = fn->ntmp;<br />
stk = emalloc(nt * sizeof stk[0]);<br />
d = debug['L'];<br />
debug['L'] = 0;<br />
filldom(fn);<br />
if (debug['N']) {<br />
fprintf(stderr, "\n> Dominators:\n");<br />
for (b1=fn->start; b1; b1=b1->link) {<br />
if (!b1->dom)<br />
continue;<br />
fprintf(stderr, "%10s:", b1->name);<br />
for (b=b1->dom; b; b=b->dlink)<br />
fprintf(stderr, " %s", b->name);<br />
fprintf(stderr, "\n");<br />
}<br />
}<br />
fillfron(fn);<br />
filllive(fn);<br />
phiins(fn);<br />
renblk(fn->start, stk, fn);<br />
while (nt--)<br />
while ((n=stk[nt])) {<br />
stk[nt] = n->up;<br />
nfree(n);<br />
}<br />
debug['L'] = d;<br />
free(stk);<br />
if (debug['N']) {<br />
fprintf(stderr, "\n> After SSA construction:\n");<br />
printfn(fn, stderr);<br />
}<br />
}</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=All.h&diff=106All.h2018-03-26T17:38:59Z<p>Admin: </p>
<hr />
<div> [[Структура Fn | struct Fn]]<br />
[[Структура_Tmp | struct Tmp]]<br />
[[Структура_Blk | struct Blk]]<br />
[[Структура_Ins | struct Ins]]<br />
[[Структура_Ref | struct Ref]]<br />
[[Структура_Op | struct Op]]<br />
[[Структура_Use | struct Use]]<br />
[[Tmp0]]<br />
/* ssa.c */<br />
[[Функция_filluse | void filluse(Fn *)]]<br />
[[Функция_ssa | void ssa(Fn *)]]<br />
/* cfg.c */<br />
[[Функция_fillpreds | void fillpreds(Fn *)]]<br />
[[Функция_fillrpo | void fillrpo(Fn *)]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=81Заглавная страница2018-03-25T13:10:33Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# [[FAQ | Различные проблемы]], которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые [[Теория к заданиям | теоретические части]] из лекций.<br />
<br />
== Документация QBE ==<br />
Оригинальная документация расположена на сайте [http://c9x.me/compile/ c9x.me].<br />
Перевод оригинальной документации на Wiki:<br />
<br />
# [[QBE]]<br />
# Типы<br />
## [[Простые типы данных]]<br />
## [[Подтипы | Подтипирование]]<br />
# [[Константы]]<br />
# [[Объявления]]<br />
## [[Составные типы данных]]<br />
## [[Data]]<br />
## [[Функции]]<br />
# Управление<br />
## [[Блоки]]<br />
## [[Переходы]]<br />
# [[Инструкции]]<br />
## [[Арифметические и битовые операции]]<br />
## [[Память]]<br />
## [[Сравнения]]<br />
## [[Преобразования]]<br />
## [[Инструкции Cast и Copy]]<br />
## [[Инструкция Call]]<br />
## [[Вариативность]]<br />
## [[Инструкция Phi]]<br />
# [[Инструкции QBE | Список всех инструкций]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=80Заглавная страница2018-03-25T12:56:04Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# [[FAQ | Различные проблемы]], которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые теоретические части из лекций.<br />
<br />
== Документация QBE ==<br />
Оригинальная документация расположена на сайте [http://c9x.me/compile/ c9x.me].<br />
Перевод оригинальной документации на Wiki:<br />
<br />
# [[QBE]]<br />
# Типы<br />
## [[Простые типы данных]]<br />
## [[Подтипы | Подтипирование]]<br />
# [[Константы]]<br />
# [[Объявления]]<br />
## [[Составные типы данных]]<br />
## [[Data]]<br />
## [[Функции]]<br />
# Управление<br />
## [[Блоки]]<br />
## [[Переходы]]<br />
# [[Инструкции]]<br />
## [[Арифметические и битовые операции]]<br />
## [[Память]]<br />
## [[Сравнения]]<br />
## [[Преобразования]]<br />
## [[Инструкции Cast и Copy]]<br />
## [[Инструкция Call]]<br />
## [[Вариативность]]<br />
## [[Инструкция Phi]]<br />
# [[Инструкции QBE | Список всех инструкций]]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BD%D1%81%D1%82%D0%B0%D0%BD%D1%82%D1%8B&diff=79Константы2018-03-24T13:44:49Z<p>Admin: </p>
<hr />
<div> CONST :=<br />
['-'] NUMBER # Десятичное целое число<br />
| 's_' FP # Число одинарной точности<br />
| 'd_' FP # Число двойной точности<br />
| $IDENT # Глобальный символ<br />
<br />
В [[QBE | промежуточном языке]] константы задаются с помощью единого синтаксиса и семантики. Константы используются явно, непосредственно в инструкциях; нет необходимости в команде «загрузки константы» (из памяти).<br />
<pre>Throughout the IL, constants are specified with a unified syntax and semantics. Constants are immediates, meaning that they can be used directly in instructions; there is no need for a "load constant" instruction.</pre><br />
<br />
Представление целых чисел является [https://ru.wikipedia.org/wiki/Дополнительный_код дополнительным кодом]. Числа с плавающей запятой представлены с использованием одноточечных и двухточечных форматов стандарта [https://en.wikipedia.org/wiki/IEEE_754 IEEE 754].<br />
<pre>The representation of integers is two's complement. Floating-point numbers are represented using the single-precision and double-precision formats of the IEEE 754 standard.</pre><br />
<br />
Константы определяют последовательность бит и являются нетипизированными. Они всегда анализируются как 64-битные блобы (прим. примерно тоже самое, что кластер). В зависимости от контекста, окружающего константу, могут использоваться только некоторые из ее битов. Например, в приведенной ниже программе обе указанные переменные имеют одинаковое значение, так как первый операнд вычитания представляет собой w - word (32-бит) контекст.<br />
<pre>Constants specify a sequence of bits and are untyped. They are always parsed as 64-bit blobs. Depending on the context surrounding a constant, only some of its bits are used. For example, in the program below, the two variables defined have the same value since the first operand of the subtraction is a word (32-bit) context.</pre><br />
<br />
%x =w sub -1, 0<br />
%y =w sub 4294967295, 0<br />
<br />
Поскольку указание констант с плавающей запятой на их биты делает код менее читаемым, то для их выражения предоставляется [https://ru.wikipedia.org/wiki/Синтаксический_сахар синтаксический сахар]. Стандартная экспоненциальная запись имеет префикс <code>s_</code> и <code>d_</code> для чисел с одной и двумя точками соответственно. Следующий пример определяет дважды ту же константу с двойной точностью.<br />
<pre>Because specifying floating-point constants by their bits makes the code less readable, syntactic sugar is provided to express them. Standard scientific notation is prefixed with s_ and d_ for single and double precision numbers respectively. Once again, the following example defines twice the same double-precision constant.</pre><br />
<br />
%x =d add d_0, d_-1<br />
%y =d add d_0, -4616189618054758400<br />
<br />
Глобальные символы также могут использоваться непосредственно как константы; они будут разрешены и превращены в фактические числовые константы компоновщиком.<br />
<pre>Global symbols can also be used directly as constants; they will be resolved and turned into actual numeric constants by the linker.</pre></div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%D0%BC&diff=78Теория к заданиям2018-03-23T16:12:47Z<p>Admin: </p>
<hr />
<div>== Множества Gen и Kill ==<br />
<br />
В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output).<br />
*gen – множество определений, порождаемых инструкцией<br />
*kill – множество определений, убиваемых инструкцией<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:<br />
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;<br />
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.<br />
<br />
== Достигающие определения ==<br />
<br />
Из лекций:<br />
*<strong>Определением переменной x</strong> называется инструкция, которая<br />
присваивает значение переменной <code>х</code>.<br />
*<strong>Использованием переменной x</strong> является инструкция, одним из<br />
операндов которой является переменная <code>х</code>.<br />
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее<br />
определение.<br />
*Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым.<br />
<br />
<div style="float:right;">[[File:RDexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
Начало блока B2 достигается определениями:<br />
*(i, B1), (j, B1), (a, B1),<br />
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)<br />
*(a, B3)<br />
*(i, B4)<br />
<br />
(i, B2) не достигает начала B2, так как его убивает (i, B4)<br />
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> <br />
Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia].<br />
<br />
== Множества Def и Use ==<br />
<br />
*def – множество переменных, определяемых в блоке В до их использования в этом блоке (любая переменная из defB мертва на входе в блок В).<br />
*use – множество переменных, используемых в блоке В до их определения в этом блоке (любая переменная из useB жива на входе в блок В).<br />
<br />
<div style="float:right;">[[File:DUexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
*в блоке B2 переменные i и j используются до их переопределения, следовательно,<br />
useB2 = {(i,B1), (i,B4), (j,B1)} = (1100001)<br />
<br />
*в блоке B2 определяются новые значения переменных i и j, так что<br />
defB2 = {(i,B2), (j,B2)} = (0001100)<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Пример алгоритма и дополнительную информацию можно найти на [https://github.com/wisestump/OptimizingCompiler/blob/4105258f3865a6ebed70a1445fbf1f1df264a61c/documentation/PiedPiper/PiedPiper-DefUseCalculation.md github]. <br />
<u>Обратите внимание</u>, в примерах следующего вида:<br />
export function w $f(w %n, w %m) {<br />
@start<br />
%a =w add 1, 1<br />
@end<br />
ret %a<br />
}<br />
переменная <code>%a</code> должна входить в <code>use(ret)</code>.<br />
<br />
== Живые переменные ==<br />
<br />
Для определения переменной x в точке p программы выяснить, будет ли указанное значение x использоваться вдоль какого-нибудь пути, начинающемся в точке p.<br />
*Если да – переменная x жива (активна) в точке p.<br />
*Если нет – переменная x мертва (неактивна) в точке p.<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Фактически, это Reaching Definitions (Достигающие определения) наоборот. <br />
Пример алгоритма.<br />
for (каждый базовый блок B) {<br />
In[B] = ∅<br />
}<br />
while (внесены изменения в In) {<br />
for (каждый базовый блок, отличный от выходного) {<br />
Out[B] = ⋃In[S], S - преемник В<br />
In[B] = use[B] ∪ (Out[B] \ def[B])<br />
}<br />
}<br />
Тогда живые переменные блока - это его Out.<br />
<br />
== Доминаторы ==<br />
Из лекций:<br />
В [https://ru.wikipedia.org/wiki/Граф_потока_управления ГПУ] вершина <code>d</code> является <strong>доминатором</strong> вершины <code>n</code> (этот факт записывается как <code>d dom n</code> или <code>d = Dom(n))</code>, если любой путь от вершины <code>Entry</code> до вершины <code>n</code> проходит через вершину <code>d</code>.<br />
<br />
Другой вариант определения. <br />
Узел <code>d</code> графа потока доминирует над узлом <code>n</code>, если любой путь от входного узла графа потока к <code>n</code> проходит через <code>d</code>. Заметим, что при таком определении каждый узел доминирует над самим собой.<br />
<br />
== Форма SSA ==<br />
Из лекций:<br />
Форма статического единственного присваивания (SSA) позволяет в каждой точке программы объединить<br />
*информацию об имени переменной<br />
*с информацией о текущем значении этой переменной (или, что то же самое, с информацией о том, какое из определений данной переменной определяет ее текущее значение в данной точке).<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> Вы также можете почерпнуть некоторую дополнительную информацию в соответствующей статье на [https://ru.wikipedia.org/wiki/SSA Wikipedia].</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%D0%BC&diff=77Теория к заданиям2018-03-23T16:12:28Z<p>Admin: </p>
<hr />
<div>== Множества Gen и Kill ==<br />
<br />
В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output).<br />
*gen – множество определений, порождаемых инструкцией<br />
*kill – множество определений, убиваемых инструкцией<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:<br />
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;<br />
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.<br />
<br />
== Достигающие определения ==<br />
<br />
Из лекций:<br />
*<strong>Определением переменной x</strong> называется инструкция, которая<br />
присваивает значение переменной <code>х</code>.<br />
*<strong>Использованием переменной x</strong> является инструкция, одним из<br />
операндов которой является переменная <code>х</code>.<br />
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее<br />
определение.<br />
*Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым.<br />
<br />
<div style="float:right;">[[File:RDexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
Начало блока B2 достигается определениями:<br />
*(i, B1), (j, B1), (a, B1),<br />
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)<br />
*(a, B3)<br />
*(i, B4)<br />
<br />
(i, B2) не достигает начала B2, так как его убивает (i, B4)<br />
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> <br />
Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia].<br />
<br />
== Множества Def и Use ==<br />
<br />
*def – множество переменных, определяемых в блоке В до их использования в этом блоке (любая переменная из defB мертва на входе в блок В).<br />
*use – множество переменных, используемых в блоке В до их определения в этом блоке (любая переменная из useB жива на входе в блок В).<br />
<br />
<div style="float:right;">[[File:DUexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
*в блоке B2 переменные i и j используются до их переопределения, следовательно,<br />
useB2 = {(i,B1), (i,B4), (j,B1)} = (1100001)<br />
<br />
*в блоке B2 определяются новые значения переменных i и j, так что<br />
defB2 = {(i,B2), (j,B2)} = (0001100)<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Пример алгоритма и дополнительную информацию можно найти на [https://github.com/wisestump/OptimizingCompiler/blob/4105258f3865a6ebed70a1445fbf1f1df264a61c/documentation/PiedPiper/PiedPiper-DefUseCalculation.md github]. <br />
<u>Обратите внимание</u>, в примерах следующего вида:<br />
export function w $f(w %n, w %m) {<br />
@start<br />
%a =w add 1, 1<br />
@end<br />
ret %a<br />
}<br />
переменная <code>%a</code> должна входить в <code>use(ret)</code>.<br />
<br />
== Живые переменные ==<br />
<br />
Для определения переменной x в точке p программы выяснить, будет ли указанное значение x использоваться вдоль какого-нибудь пути, начинающемся в точке p.<br />
*Если да – переменная x жива (активна) в точке p.<br />
*Если нет – переменная x мертва (неактивна) в точке p.<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Фактически, это Reaching Definitions (Достигающие определения) наоборот. <br />
Пример алгоритма.<br />
for (каждый базовый блок B) {<br />
In[B] = ∅<br />
}<br />
while (внесены изменения в In) {<br />
for (каждый базовый блок, отличный от выходного) {<br />
Out[B] = ⋃In[S], S - преемник В<br />
In[B] = use[B] ∪ (Out[B] \ def[B])<br />
}<br />
}<br />
Тогда живые переменные блока - это его Out.<br />
<br />
== Доминаторы ==<br />
Из лекций:<br />
В [https://ru.wikipedia.org/wiki/Граф_потока_управления ГПУ] вершина <code>d</code> является <strong>доминатором</strong> вершины <code>n</code> (этот факт записывается как <code>d dom n</code> или <code>d = Dom(n))</code>, если любой путь от вершины <code>Entry</code> до вершины <code>n</code> проходит через вершину <code>d</code>.<br />
<br />
Другой вариант определения. <br />
Узел <code>d</code> графа потока доминирует над узлом <code>n</code>, если любой путь от входного узла графа потока к <code>n</code> проходит через <code>d</code>. Заметим, что при таком определении каждый узел доминирует над самим собой.<br />
<br />
== Форма SSA ==<br />
Из лекций:<br />
Форма статического единственного присваивания (SSA) позволяет в каждой точке программы объединить<br />
*информацию об имени переменной<br />
*с информацией о текущем значении этой переменной (или, что то же самое, с информацией о том, какое из определений данной переменной определяет ее текущее значение в данной точке).<br />
<br />
<strong>Примечание от нерадивых студентов.</strong>. Вы также можете почерпнуть некоторую дополнительную информацию в соответствующей статье на [https://ru.wikipedia.org/wiki/SSA Wikipedia].</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%D0%BC&diff=74Теория к заданиям2018-03-23T14:46:13Z<p>Admin: </p>
<hr />
<div>== Множества Gen и Kill ==<br />
<br />
В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output).<br />
*gen – множество определений, порождаемых инструкцией<br />
*kill – множество определений, убиваемых инструкцией<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:<br />
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;<br />
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.<br />
<br />
== Достигающие определения ==<br />
<br />
Из лекций:<br />
*<strong>Определением переменной x</strong> называется инструкция, которая<br />
присваивает значение переменной <code>х</code>.<br />
*<strong>Использованием переменной x</strong> является инструкция, одним из<br />
операндов которой является переменная <code>х</code>.<br />
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее<br />
определение.<br />
*Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым.<br />
<br />
<div style="float:right;">[[File:RDexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
Начало блока B2 достигается определениями:<br />
*(i, B1), (j, B1), (a, B1),<br />
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)<br />
*(a, B3)<br />
*(i, B4)<br />
<br />
(i, B2) не достигает начала B2, так как его убивает (i, B4)<br />
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> <br />
Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia].</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%D0%BC&diff=73Теория к заданиям2018-03-23T14:44:06Z<p>Admin: </p>
<hr />
<div>== Множества Gen и Kill ==<br />
<br />
В лекциях определения этих множеств даются в рамках темы Достигающих определений (Тема №2. Построение множеств Input и Output).<br />
*gen – множество определений, порождаемых инструкцией<br />
*kill – множество определений, убиваемых инструкцией<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:<br />
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;<br />
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.<br />
<br />
== Достигающие определения ==<br />
<br />
Из лекций:<br />
*<strong>Определением переменной x</strong> называется инструкция, которая<br />
присваивает значение переменной <code>х</code>.<br />
*<strong>Использованием переменной x</strong> является инструкция, одним из<br />
операндов которой является переменная <code>х</code>.<br />
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее<br />
определение.<br />
*Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым.<br />
<br />
<div style="float:right;">[[File:RDexample.png | 100px]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
Начало блока B2 достигается определениями:<br />
*(i, B1), (j, B1), (a, B1),<br />
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)<br />
*(a, B3)<br />
*(i, B4)<br />
<br />
(i, B2) не достигает начала B2, так как его убивает (i, B4)<br />
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> <br />
Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia].</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:RDexample.png&diff=72Файл:RDexample.png2018-03-23T14:41:49Z<p>Admin: </p>
<hr />
<div></div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D1%8F%D0%BC&diff=71Теория к заданиям2018-03-23T14:37:02Z<p>Admin: Новая страница: «== Множества Gen и Kill == В лекциях определения этих множеств даются в рамках темы Достигающ…»</p>
<hr />
<div>== Множества Gen и Kill ==<br />
<br />
В лекциях определения этих множеств даются в рамках темы Достигающих определений (Тема №2. Построение множеств Input и Output).<br />
*gen – множество определений, порождаемых инструкцией<br />
*kill – множество определений, убиваемых инструкцией<br />
<br />
<strong>Примечание от нерадивых студентов.</strong><br />
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:<br />
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;<br />
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.<br />
<br />
== Достигающие определения ==<br />
<br />
Из лекций:<br />
*<strong>Определением переменной x</strong> называется инструкция, которая<br />
присваивает значение переменной <code>х</code>.<br />
*<strong>Использованием переменной x</strong> является инструкция, одним из<br />
операндов которой является переменная <code>х</code>.<br />
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее<br />
определение.<br />
*Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым.<br />
<br />
<div style="float:right;"><img src="http://compilers.csmsu.ru/images/RDexample.png">[[File:RDexample.png|20px|link=http://compilers.csmsu.ru/images/RDexample.png]]</div><br />
<strong>Пример. (Из лекций).</strong><br />
<u>B1</u><br />
i ← –, m, 1<br />
j ← n<br />
a ← u1<br />
<br />
<u>B2</u><br />
i ← +, i, 1<br />
j ← -, j, 1 a<br />
<br />
<u>B3</u><br />
a ← u2<br />
<br />
<u>B4</u><br />
i ← u3<br />
<br />
Начало блока B2 достигается определениями:<br />
*(i, B1), (j, B1), (a, B1),<br />
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)<br />
*(a, B3)<br />
*(i, B4)<br />
<br />
(i, B2) не достигает начала B2, так как его убивает (i, B4)<br />
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4<br />
<br />
<strong>Примечание от нерадивых студентов.</strong> <br />
Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia].</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=70Заглавная страница2018-03-21T12:55:16Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# [[FAQ | Различные проблемы]], которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые теоретические части из лекций.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=69Заглавная страница2018-03-21T12:55:00Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# [[http://compilers.csmsu.ru/wiki/FAQ | Различные проблемы]], которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые теоретические части из лекций.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=68Заглавная страница2018-03-21T12:54:41Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# [http://compilers.csmsu.ru/wiki/FAQ Различные проблемы], которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые теоретические части из лекций.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BA%D0%BE%D0%B4%D0%B0_QBE_IL&diff=63Примеры кода QBE IL2018-03-20T16:17:31Z<p>Admin: </p>
<hr />
<div><strong>ВАЖНО!</strong> Пожалуйста, обратите внимание, некоторые операции, приведенные в примерах, используются без "левой части" (например, <code>%x = w ...</code>). Это не ошибка, примеры имеют такой вид исключительно ради наглядности и конкретизации тем, обозначенных в заголовках примеров.<br />
<br />
== Операции и операнды ==<br />
Рассмотрим некоторые операции и операнды в [[QBE]].<br />
<br />
Подробнее можно прочитать в разделе [[Арифметические и битовые операции]].<br />
Обычная арифметика - сложение (add), вычитание (sub), деление (div), умножение (mul). Каждая из этих операций требует два аргумента/операнда (очевидно). <br />
<br />
Примеры.<br />
<br />
add 0, 1 <br />
К нулю (первое слагаемое/первый аргумент/операнд) прибавляется единица (второе слагаемое/второй аргумент/операнд). Результатом сложения (сумма) будет число 1.<br />
<br />
sub 2, 1<br />
Из двойки (уменьшаемое/первый аргумент/операнд) вычитается единица (вычитаемое/второй аргумент/операнд). Результатом вычитания (разностью) будет число 1.<br />
<br />
div 4, 2<br />
Четыре (делимое/первый аргумент/операнд) делится на два (делитель/второй аргумент/операнд). Результатом деления (частным) будет число 2.<br />
<br />
mul 2, 2<br />
Два (первый множитель/первый аргумент/операнд) умножается на два (второй множитель/второй аргумент/операнд). Результатом умножения (произведением) будет число 4.<br />
<br />
Аналогично для логических операций.<br />
Для операций сдвига справедливо требование наличие двух аргументов/операндов. В этом случае первый аргумент/операнд будет являться тем, что требуется "сдвинуть", а второй – числом (целым), на которое требуется осуществить сдвиг.<br />
<br />
Операции над [[Память | памятью]].<br />
<br />
Основные операции для работы с памятью, которые могут понадобиться Вам для взаимодействия с массивами данных – <code>store</code> и <code>load</code>. Особенности применения описаны в соответствующей статье, как на данном ресурсе, так и в [https://c9x.me/compile/ оригинальной документации]. Приведем пример использования этих команд.<br />
<br />
storeb 0, %array<br />
Разместит в первый байт массива <code>array</code> (то есть <code>%array</code> выступает аналогом <code>array[0]</code>) число 0. Суффикс <code>b</code> на конце инструкции <code>store</code> свидетельствует о типе используемых операндов.<br />
<br />
loadub %array<br />
Результатом выполнения инструкции будет усеченное до unsigned (беззнаковое) значение первого байта массива <code>array</code>. Суффиксы <code>u</code> и <code>b</code> означают unsigned (беззнаковое) и byte (байт) соответственно. То есть суффиксы инструкции <code>load</code> накладывают ограничение на возвращаемый результат.<br />
<br />
Подробнее о работе с массивами будет рассказано ниже.<br />
<br />
== Присваивания ==<br />
<br />
Пример кода на Си.<br />
int a = 1;<br />
int b = 2;<br />
int c;<br />
c = a + b;<br />
<br />
Аналогичный код на QBE IL.<br />
%a = w add 0, 1<br />
%b = w add 0, 2<br />
%c = w add %a, %b<br />
<br />
== Блоки ==<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
Результатом выполнения будет <code> c = 3 </code>, а без наличия переходов между блоками каждая инструкция будет выполняться последовательно. То есть в блоке <code>@start</code> в переменную <code>b</code> будет помещено число 5. Затем мы попадем в блок <code>@initA</code>, где объявим переменную <code>a</code> и положим в нее число 1. Далее, в блоке <code>@initB</code> уже размещенное в переменной <code>b</code> будет заменено на число 2. В блоке <code>@result</code> объявляется переменная <code>c</code> и инициализируется суммой переменных <code>a</code> и <code>b</code>, эта сумма будет равна 3 (1+2). Блок <code>@end</code> осуществит выход из функции.<br />
<br />
== Сравнения ==<br />
<br />
Вы можете найти более подробную информацию в разделе [[Сравнения]]. Все сравнения, реализованные в [[QBE | промежуточном языке]] практически идентичны сравнениям в языке ассемблера. Главным образом, сравнения применяются для осуществления управления условными переходами (представлено ниже). В [[QBE | промежуточном языке]] представлено несколько видов сравнения для разных типов данных: сравнение на равенство аргументов/операндов, сравнение на неравенство аргументов/операндов, сравнение на "больше или равно", сравнение на "меньше или равно", сравнение на "меньше", сравнение на "больше".<br />
<br />
%condition = w cslew %a, %b<br />
Данный пример сравнивает две переменных размерности w (word) (о чем свидетельствует окончание инструкции - <code>w</code>) на "меньше или равно" (суффикс <code>le</code> означает "lower or equal") и возвращает 0 размерности w (word) в случае, если <code>%b</code> больше <code>%a</code>, либо 1 размерности w (word) в случае положительного выполнения условий суффикса. <br />
<br />
== Переходы ==<br />
<br />
Рассмотрим код из предыдущего примера с "Блоками", но внесем одно изменение – установим безусловный переход <code>jmp</code> на другой блок в блоке <code>@initA</code>. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
jmp @result<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
При выполнении, с помощью <code>jmp @result</code> после объявления переменной <code>a</code> выполнение продолжится не последовательно (в блоке <code>@initB</code>), а с блока <code>@result</code>. То есть <code>c = 1 + 5</code> (не произойдет переприсваивания <code>b = 2</code>), тем самым, результатом в <code>c</code> будет являться число 6.<br />
<br />
Заменим безусловный переход <code>jmp @result</code> из примера выше на переход по условию <code>%condition</code>, которое добавим перед переходом. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
%condition = w cslew %a, 2<br />
jnz %condition, @result, @initB<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
В данном случае, условие <code>%condition = w cslew %a, 2</code> всегда будет выполняться, а переход <code>jnz %condition, @result, @initB</code> всегда будет переходить на ветвь <code>@result</code>. Но если сравнение, например, в <code>@initA</code> в переменную <code>%a</code> положить не 1, а 3, то условие будет всегда ложным, тогда переход будет всегда выполняться на ветвь <code>@initB</code>, и результатом выполнения программы будет <code>%c = 3 (т.к. a = 3) + 2 (т.к. в b будет лежать 2) = 5</code><br />
<br />
== Массивы ==<br />
<br />
Предположим, у нас имеется массив байтов <code>array</code> неопределенного размера и некоторое целое беззнаковое число N. Для работы с N-ным элементом массива придется завести дополнительную переменную (дабы не утратить указатель на первые N элементов), в которой будет размещена сумма адреса первого элемента массива и сдвига на N байт.<br />
%arrayN = l add %array, %N<br />
Теперь с помощью <code>arrayN</code> и инструкций <code>load</code> и <code>store</code> можно получить и записать (соответственно) в N-ный элемент массива <code>array</code>.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=62Заглавная страница2018-03-20T15:38:37Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса [https://compilers.ispras.ru/cmc "Конструирование компиляторов"], читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# Различные проблемы, которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые теоретические части из лекций.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=QBE&diff=61QBE2018-03-20T15:37:20Z<p>Admin: </p>
<hr />
<div><strong>QBE IL (QBE intermediate language)</strong> - промежуточный язык, является языком более высокого уровня, чем язык ассемблера. Он сглаживает большинство проблем базового оборудования и позволяет использовать бесконечное количество временных конструкций. Этот более высокий уровень абстракции позволяет сторонним программистам сосредоточиться на проблемах разработки языка.<br />
<pre>The intermediate language (IL) is a higher-level language than the machine's assembly language. It smoothes most of the irregularities of the underlying hardware and allows an infinite number of temporaries to be used. This higher abstraction level allows frontend programmers to focus on language design issues.</pre><br />
<br />
<div>__TOC__</div><br />
<br />
== Входные файлы ==<br />
<br />
Промежуточный язык предоставляется QBE в виде текста. Как правило, один файл создается для каждой программы с входного языка интерфейса. IL-файл представляет собой последовательность определений для данных, функций и типов. После обработки QBE полученный файл может быть собран и связан с использованием стандартного инструментального ПО (например, [https://ru.wikipedia.org/wiki/GNU_Binutils GNU_binutils]).<br />
<pre>The intermediate language is provided to QBE as text. Usually, one file is generated per each compilation unit from the frontend input language. An IL file is a sequence of Definitions for data, functions, and types. Once processed by QBE, the resulting file can be assembled and linked using a standard toolchain (e.g., GNU binutils).</pre><br />
<br />
Ниже приведено полное содержимое IL-файла "Hello World", в котором определена функция, выводящая на экран "hello world". Поскольку строка не является объектом штатным объектом (только указатель) языка, она определяется вне тела функции. Комментарии начинаются с символа <strong>#</strong> и заканчиваются концом строки.<br />
<pre>Here is a complete "Hello World" IL file which defines a function that prints to the screen. Since the string is not a first class object (only the pointer is) it is defined outside the function's body. Comments start with a # character and finish with the end of the line.</pre><br />
<br />
# Объявление константной строки "hello world"<br />
data $str = { b "hello world", b 0 }<br />
<br />
function w $main() {<br />
@start<br />
# Вызов функции puts с аргументом $str.<br />
%r =w call $puts(l $str)<br />
ret 0<br />
}<br />
<br />
Если вы прочитали ссылку про язык [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM], вы можете понять вышеприведенный код. В сравнении, QBE предоставляет гораздо более простое использование типов и синтаксиса.<br />
<pre>If you have read the LLVM language reference, you might recognize the example above. In comparison, QBE makes a much lighter use of types and the syntax is terser.</pre><br />
<br />
== Запись БНФ == <br />
<br />
Синтаксис языка, который Вы сможете найти в разделах данной Wiki (и в оригинальной документации), описан с использованием [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ]. Различные используемые конструкции [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] перечислены ниже.<br />
<br />
Ключевые слова заключены в кавычки;<br />
... | ... выражает дизъюнкции;<br />
[ ... ] обозначает некоторый синтаксис как необязательный;<br />
( ... ), обозначает разделенный запятыми список прилагаемого синтаксиса;<br />
...* и ...+ используются для произвольных обозначений и для повторений соответственно.<br />
<br />
== Символы ==<br />
<br />
Промежуточный язык изобилует разными символами, все пользовательские имена выделяются символьным префиксом. Это делается для предотвращения конфликтов ключевых слов, а также для быстрого определения области видимости и характера идентификаторов.<br />
<pre>The intermediate language makes heavy use of sigils, all user-defined names are prefixed with a sigil. This is to avoid keyword conflicts, and also to quickly spot the scope and nature of identifiers.</pre><br />
<br />
<code>:</code> используется для определенных пользователем [[Составные типы данных | составных типов данных]]<br />
<code>$</code> используется для глобальных переменных (представленных в виде указателя)<br />
<code>%</code> используется для переменных внутри [[Функции | функций]]<br />
<code>@</code> используется для обозначения меток [[Блоки | блоков]]<br />
<br />
В этом синтаксисе [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] мы используем <code>?IDENT</code> для обозначения идентификатора, начинающегося с символа <code>?</code>.<br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Basic-Concepts c9x.me]<br />
<br />
== Сравнение с LLVM ==<br />
QBE и LLVM являются компиляторами, использующими представление SSA. В этом документе объясняется, почему LLVM не делает QBE лишним. Очевидно, что все следующее предвзято, потому что написано мной (разработчиком).<br />
<pre>Both QBE and LLVM are compiler backends using an SSA representation. This document will explain why LLVM does not make QBE a redundant project. Obviously, everything following is biased, because written by me.</pre><br />
<br />
==== Объем ====<br />
<br />
QBE - проект гораздо меньшего масштаба с разными целями, чем LLVM.<br />
<pre>QBE is a much smaller scale project with different goals than LLVM.</pre><br />
*QBE предназначен для разработчиков своего языка.<br />
<pre>QBE is for amateur language designers.</pre><br />
<br />
Он не затрагивает все проблемы, возникающие при разработке языка технического уровня. Если вы "играете" с некоторыми языками, использование LLVM будет походить на таскание вашего рюкзака с грузовиком, а использование QBE будет больше похоже на катание на велосипеде.<br />
<pre>It does not address all the problems faced when conceiving an industry-grade language. If you are toying with some language ideas, using LLVM will be like hauling your backpack with a truck, but using QBE will feel more like riding a bicycle.</pre<br />
<br />
*QBE - это первые 70%, а не последние 30%.<br />
<pre>QBE is about the first 70%, not the last 30%.</pre><br />
<br />
QBE пытается точно определить в многочисленной литературе о компиляции те оптимизации, которые дают вам 70% производительности в 10% кода в полномасштабных компиляторах.<br />
<pre>It attempts to pinpoint, in the extremely vast compilation literature, the optimizations that get you 70% of the performance in 10% of the code of full blown compilers.</pre<br />
Например, перевод в форму [https://ru.wikipedia.org/wiki/SSA SSA] реализован в 160 строках кода в QBE!<br />
<pre>For example, copy propagation on SSA form is implemented in 160 lines of code in QBE!</pre><br />
<br />
*QBE чрезвычайно открыт, прост и удобен в изучении.<br />
<pre>QBE is extremely hackable.</pre><br />
<br />
Во-первых, QBE есть и останется небольшим проектом (менее 8 KLOC, прим. 1 KLOCK (Kilo Lines Of Code) = 1000 строк кода.). Во-вторых, он реализован на непривлекательном C99 без каких-либо зависимостей. В-третьих, он может переводить в промежуточный язык и отлаживать информацию в едином формате после каждого прохода.<br />
<pre>First, it is, and will remain, a small project (less than 8 kloc). Second, it is programmed in non-fancy C99 without any dependencies. Third, it is able to dump the IL and debug information in a uniform format after each pass.</pre><br />
<br />
==== Особенности ====<br />
LLVM определенно более изобилует функциями, но в QBE есть интересных несколько вещей.<br />
<pre>LLVM is definitely more packed with features, but there are a few things provided in QBE to consider.</pre><br />
<br />
*LLVM НЕ обеспечивает вам полную совместимость с Си.<br />
<pre>LLVM does NOT provide full C compatibility for you.</pre><br />
<br />
В более технических терминах любой язык, который обеспечивает хорошую совместимость с Си и использует [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] в качестве платформы, должен переопределять большие куски [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] в своем интерфейсе! Эта хорошо известная проблема в сообществе [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] вызывает много дублирования и ошибок. Реализация готового Си [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] (с аргументами структуры и возвратами) невероятно сложна, и не слишком весела. QBE предоставляет вам операции промежуточного языка для вызова (и вызывается с) без лишних проблем. Кроме того, реализация [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] в QBE была тщательно протестирована путем испытаний вручную.<br />
<pre>In more technical terms, any language that provides good C compatibility and uses LLVM as a backend needs to reimplement large chunks of the ABI in its frontend! This well known issue in the LLVM community causes a great deal of duplication and bugs. Implementing a complete C ABI (with struct arguments and returns) is incredibly tricky, and not really a lot of fun. QBE provides you with IL operations to call in (and be called by) C with no pain. Moreover the ABI implementation in QBE has been thoroughly tested by fuzzing and manual tests.</pre><br />
<br />
*LLVM IL более загроможден операциями памяти.<br />
<pre>LLVM IL is more cluttered with memory operations.</pre><br />
<br />
Реализация конструкции [https://ru.wikipedia.org/wiki/SSA SSA] сложна. Чтобы уберечь своих пользователей от необходимости его реализации, [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] предоставляет части стека. Это означает, что одно увеличение на 1 переменной <code>v</code> будет состоять из трех инструкций [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM]: одна выгрузка, одно добавление и одно сохранение. QBE предоставляет простые типы переменных, отличные от [https://ru.wikipedia.org/wiki/SSA SSA], поэтому увеличение <code>v</code> выполняется просто с помощью одной команды <code>%v = w add% v, 1</code>. Это может показаться визуальным преимуществом, но увеличение количества команд из одной до трех упрощает для разработчиков выявление ошибок в сгенерированном коде.<br />
<pre>Implementing SSA construction is hard. To save its users from having to implement it, LLVM provides stack slots. This means that one increment of a variable v will be composed of three LLVM instructions: one load, one add, and one store. QBE provides simple non-SSA temporaries, so incrementing v is simply done with one instruction %v =w add %v, 1. This could seem cosmetic, but dividing the size of the IL by three makes it easier for the frontend writers to spot bugs in the generated code.</pre><br />
<br />
*LLVM IL более загроможден с объявлениями и преобразованиями типов.<br />
<pre>LLVM IL is more cluttered with type annotations and casts.</pre><br />
<br />
Для улучшения оптимизации и корректности [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] имеет сложные типы промежуточного представления. Тем не менее, только несколько типов действительно являются первоклассными, и многие операции с исходными языками требуют компиляции списков. Поскольку QBE реализует гораздо более простое использование типов, промежуточное представление более читабельно и короче. Разумеется, можно утверждать, что достоинства QBE не столь велики, но помните, что на практике большое количество преобразований, необходимых в ILL LLVM, подрывает общую эффективность системы типов.<br />
<pre>For the sake of advanced optimizations and correctness, LLVM has complex IL types. However, only a few types are really first class and many operations of source languages require casts to be compiled. Because QBE makes a much lighter use of types, the IL is more readable and shorter. It can of course be argued back that the correctness of QBE is jeoparadized, but remember that, in practice, the large amount of casts necessary in LLVM IL is undermining the overall effectiveness of the type system.</pre><br />
<br />
== Проекты, использующие QBE ==<br />
<br />
*Интерфейс учебника включен в дистрибутив в каталоге <code>minic/</code>. В менее чем 1000 строк он компилирует упрощенный Си. Небольшие контрольные показатели также предоставляются.<br />
*Амбициозный [http://git.suckless.org/scc/ Си компилятор].<br />
*Два интерфейса для [https://github.com/andrewchambers/qmbfc brainfuck] и [https://github.com/andrewchambers/qc Си] были написаны в Myrddin Эндрю Чэмберсом.<br />
*Свидетельством хорошей архитектуры QBE является компилятор [https://github.com/BeRo1985/pacc PACC] от Бенжамина Россо; он повторно использует как архитектуру IL, так и множество возможностей QBE.<br />
*Некоторая текущая работа над компилятором [http://myrlang.org/ Myrddin] направлена на использование QBE в качестве backend.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=QBE&diff=60QBE2018-03-20T15:36:41Z<p>Admin: </p>
<hr />
<div><strong>QBE IL (QBE intermediate language)</strong> - промежуточный язык, является языком более высокого уровня, чем язык ассемблера. Он сглаживает большинство проблем базового оборудования и позволяет использовать бесконечное количество временных конструкций. Этот более высокий уровень абстракции позволяет сторонним программистам сосредоточиться на проблемах разработки языка.<br />
<pre>The intermediate language (IL) is a higher-level language than the machine's assembly language. It smoothes most of the irregularities of the underlying hardware and allows an infinite number of temporaries to be used. This higher abstraction level allows frontend programmers to focus on language design issues.</pre><br />
<br />
<div style="float:right;">__TOC__</div><br />
<br />
== Входные файлы ==<br />
<br />
Промежуточный язык предоставляется QBE в виде текста. Как правило, один файл создается для каждой программы с входного языка интерфейса. IL-файл представляет собой последовательность определений для данных, функций и типов. После обработки QBE полученный файл может быть собран и связан с использованием стандартного инструментального ПО (например, [https://ru.wikipedia.org/wiki/GNU_Binutils GNU_binutils]).<br />
<pre>The intermediate language is provided to QBE as text. Usually, one file is generated per each compilation unit from the frontend input language. An IL file is a sequence of Definitions for data, functions, and types. Once processed by QBE, the resulting file can be assembled and linked using a standard toolchain (e.g., GNU binutils).</pre><br />
<br />
Ниже приведено полное содержимое IL-файла "Hello World", в котором определена функция, выводящая на экран "hello world". Поскольку строка не является объектом штатным объектом (только указатель) языка, она определяется вне тела функции. Комментарии начинаются с символа <strong>#</strong> и заканчиваются концом строки.<br />
<pre>Here is a complete "Hello World" IL file which defines a function that prints to the screen. Since the string is not a first class object (only the pointer is) it is defined outside the function's body. Comments start with a # character and finish with the end of the line.</pre><br />
<br />
# Объявление константной строки "hello world"<br />
data $str = { b "hello world", b 0 }<br />
<br />
function w $main() {<br />
@start<br />
# Вызов функции puts с аргументом $str.<br />
%r =w call $puts(l $str)<br />
ret 0<br />
}<br />
<br />
Если вы прочитали ссылку про язык [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM], вы можете понять вышеприведенный код. В сравнении, QBE предоставляет гораздо более простое использование типов и синтаксиса.<br />
<pre>If you have read the LLVM language reference, you might recognize the example above. In comparison, QBE makes a much lighter use of types and the syntax is terser.</pre><br />
<br />
== Запись БНФ == <br />
<br />
Синтаксис языка, который Вы сможете найти в разделах данной Wiki (и в оригинальной документации), описан с использованием [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ]. Различные используемые конструкции [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] перечислены ниже.<br />
<br />
Ключевые слова заключены в кавычки;<br />
... | ... выражает дизъюнкции;<br />
[ ... ] обозначает некоторый синтаксис как необязательный;<br />
( ... ), обозначает разделенный запятыми список прилагаемого синтаксиса;<br />
...* и ...+ используются для произвольных обозначений и для повторений соответственно.<br />
<br />
== Символы ==<br />
<br />
Промежуточный язык изобилует разными символами, все пользовательские имена выделяются символьным префиксом. Это делается для предотвращения конфликтов ключевых слов, а также для быстрого определения области видимости и характера идентификаторов.<br />
<pre>The intermediate language makes heavy use of sigils, all user-defined names are prefixed with a sigil. This is to avoid keyword conflicts, and also to quickly spot the scope and nature of identifiers.</pre><br />
<br />
<code>:</code> используется для определенных пользователем [[Составные типы данных | составных типов данных]]<br />
<code>$</code> используется для глобальных переменных (представленных в виде указателя)<br />
<code>%</code> используется для переменных внутри [[Функции | функций]]<br />
<code>@</code> используется для обозначения меток [[Блоки | блоков]]<br />
<br />
В этом синтаксисе [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] мы используем <code>?IDENT</code> для обозначения идентификатора, начинающегося с символа <code>?</code>.<br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Basic-Concepts c9x.me]<br />
<br />
== Сравнение с LLVM ==<br />
QBE и LLVM являются компиляторами, использующими представление SSA. В этом документе объясняется, почему LLVM не делает QBE лишним. Очевидно, что все следующее предвзято, потому что написано мной (разработчиком).<br />
<pre>Both QBE and LLVM are compiler backends using an SSA representation. This document will explain why LLVM does not make QBE a redundant project. Obviously, everything following is biased, because written by me.</pre><br />
<br />
==== Объем ====<br />
<br />
QBE - проект гораздо меньшего масштаба с разными целями, чем LLVM.<br />
<pre>QBE is a much smaller scale project with different goals than LLVM.</pre><br />
*QBE предназначен для разработчиков своего языка.<br />
<pre>QBE is for amateur language designers.</pre><br />
<br />
Он не затрагивает все проблемы, возникающие при разработке языка технического уровня. Если вы "играете" с некоторыми языками, использование LLVM будет походить на таскание вашего рюкзака с грузовиком, а использование QBE будет больше похоже на катание на велосипеде.<br />
<pre>It does not address all the problems faced when conceiving an industry-grade language. If you are toying with some language ideas, using LLVM will be like hauling your backpack with a truck, but using QBE will feel more like riding a bicycle.</pre<br />
<br />
*QBE - это первые 70%, а не последние 30%.<br />
<pre>QBE is about the first 70%, not the last 30%.</pre><br />
<br />
QBE пытается точно определить в многочисленной литературе о компиляции те оптимизации, которые дают вам 70% производительности в 10% кода в полномасштабных компиляторах.<br />
<pre>It attempts to pinpoint, in the extremely vast compilation literature, the optimizations that get you 70% of the performance in 10% of the code of full blown compilers.</pre<br />
Например, перевод в форму [https://ru.wikipedia.org/wiki/SSA SSA] реализован в 160 строках кода в QBE!<br />
<pre>For example, copy propagation on SSA form is implemented in 160 lines of code in QBE!</pre><br />
<br />
*QBE чрезвычайно открыт, прост и удобен в изучении.<br />
<pre>QBE is extremely hackable.</pre><br />
<br />
Во-первых, QBE есть и останется небольшим проектом (менее 8 KLOC, прим. 1 KLOCK (Kilo Lines Of Code) = 1000 строк кода.). Во-вторых, он реализован на непривлекательном C99 без каких-либо зависимостей. В-третьих, он может переводить в промежуточный язык и отлаживать информацию в едином формате после каждого прохода.<br />
<pre>First, it is, and will remain, a small project (less than 8 kloc). Second, it is programmed in non-fancy C99 without any dependencies. Third, it is able to dump the IL and debug information in a uniform format after each pass.</pre><br />
<br />
==== Особенности ====<br />
LLVM определенно более изобилует функциями, но в QBE есть интересных несколько вещей.<br />
<pre>LLVM is definitely more packed with features, but there are a few things provided in QBE to consider.</pre><br />
<br />
*LLVM НЕ обеспечивает вам полную совместимость с Си.<br />
<pre>LLVM does NOT provide full C compatibility for you.</pre><br />
<br />
В более технических терминах любой язык, который обеспечивает хорошую совместимость с Си и использует [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] в качестве платформы, должен переопределять большие куски [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] в своем интерфейсе! Эта хорошо известная проблема в сообществе [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] вызывает много дублирования и ошибок. Реализация готового Си [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] (с аргументами структуры и возвратами) невероятно сложна, и не слишком весела. QBE предоставляет вам операции промежуточного языка для вызова (и вызывается с) без лишних проблем. Кроме того, реализация [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] в QBE была тщательно протестирована путем испытаний вручную.<br />
<pre>In more technical terms, any language that provides good C compatibility and uses LLVM as a backend needs to reimplement large chunks of the ABI in its frontend! This well known issue in the LLVM community causes a great deal of duplication and bugs. Implementing a complete C ABI (with struct arguments and returns) is incredibly tricky, and not really a lot of fun. QBE provides you with IL operations to call in (and be called by) C with no pain. Moreover the ABI implementation in QBE has been thoroughly tested by fuzzing and manual tests.</pre><br />
<br />
*LLVM IL более загроможден операциями памяти.<br />
<pre>LLVM IL is more cluttered with memory operations.</pre><br />
<br />
Реализация конструкции [https://ru.wikipedia.org/wiki/SSA SSA] сложна. Чтобы уберечь своих пользователей от необходимости его реализации, [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] предоставляет части стека. Это означает, что одно увеличение на 1 переменной <code>v</code> будет состоять из трех инструкций [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM]: одна выгрузка, одно добавление и одно сохранение. QBE предоставляет простые типы переменных, отличные от [https://ru.wikipedia.org/wiki/SSA SSA], поэтому увеличение <code>v</code> выполняется просто с помощью одной команды <code>%v = w add% v, 1</code>. Это может показаться визуальным преимуществом, но увеличение количества команд из одной до трех упрощает для разработчиков выявление ошибок в сгенерированном коде.<br />
<pre>Implementing SSA construction is hard. To save its users from having to implement it, LLVM provides stack slots. This means that one increment of a variable v will be composed of three LLVM instructions: one load, one add, and one store. QBE provides simple non-SSA temporaries, so incrementing v is simply done with one instruction %v =w add %v, 1. This could seem cosmetic, but dividing the size of the IL by three makes it easier for the frontend writers to spot bugs in the generated code.</pre><br />
<br />
*LLVM IL более загроможден с объявлениями и преобразованиями типов.<br />
<pre>LLVM IL is more cluttered with type annotations and casts.</pre><br />
<br />
Для улучшения оптимизации и корректности [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] имеет сложные типы промежуточного представления. Тем не менее, только несколько типов действительно являются первоклассными, и многие операции с исходными языками требуют компиляции списков. Поскольку QBE реализует гораздо более простое использование типов, промежуточное представление более читабельно и короче. Разумеется, можно утверждать, что достоинства QBE не столь велики, но помните, что на практике большое количество преобразований, необходимых в ILL LLVM, подрывает общую эффективность системы типов.<br />
<pre>For the sake of advanced optimizations and correctness, LLVM has complex IL types. However, only a few types are really first class and many operations of source languages require casts to be compiled. Because QBE makes a much lighter use of types, the IL is more readable and shorter. It can of course be argued back that the correctness of QBE is jeoparadized, but remember that, in practice, the large amount of casts necessary in LLVM IL is undermining the overall effectiveness of the type system.</pre><br />
<br />
== Проекты, использующие QBE ==<br />
<br />
*Интерфейс учебника включен в дистрибутив в каталоге <code>minic/</code>. В менее чем 1000 строк он компилирует упрощенный Си. Небольшие контрольные показатели также предоставляются.<br />
*Амбициозный [http://git.suckless.org/scc/ Си компилятор].<br />
*Два интерфейса для [https://github.com/andrewchambers/qmbfc brainfuck] и [https://github.com/andrewchambers/qc Си] были написаны в Myrddin Эндрю Чэмберсом.<br />
*Свидетельством хорошей архитектуры QBE является компилятор [https://github.com/BeRo1985/pacc PACC] от Бенжамина Россо; он повторно использует как архитектуру IL, так и множество возможностей QBE.<br />
*Некоторая текущая работа над компилятором [http://myrlang.org/ Myrddin] направлена на использование QBE в качестве backend.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=QBE&diff=59QBE2018-03-20T15:20:06Z<p>Admin: </p>
<hr />
<div><strong>QBE IL (QBE intermediate language)</strong> - промежуточный язык, является языком более высокого уровня, чем язык ассемблера. Он сглаживает большинство проблем базового оборудования и позволяет использовать бесконечное количество временных конструкций. Этот более высокий уровень абстракции позволяет сторонним программистам сосредоточиться на проблемах разработки языка.<br />
<pre>The intermediate language (IL) is a higher-level language than the machine's assembly language. It smoothes most of the irregularities of the underlying hardware and allows an infinite number of temporaries to be used. This higher abstraction level allows frontend programmers to focus on language design issues.</pre><br />
<br />
<div style="float:right;">__TOC__</div><br />
<br />
== Входные файлы ==<br />
<br />
Промежуточный язык предоставляется QBE в виде текста. Как правило, один файл создается для каждой программы с входного языка интерфейса. IL-файл представляет собой последовательность определений для данных, функций и типов. После обработки QBE полученный файл может быть собран и связан с использованием стандартного инструментального ПО (например, [https://ru.wikipedia.org/wiki/GNU_Binutils GNU_binutils]).<br />
<pre>The intermediate language is provided to QBE as text. Usually, one file is generated per each compilation unit from the frontend input language. An IL file is a sequence of Definitions for data, functions, and types. Once processed by QBE, the resulting file can be assembled and linked using a standard toolchain (e.g., GNU binutils).</pre><br />
<br />
Ниже приведено полное содержимое IL-файла "Hello World", в котором определена функция, выводящая на экран "hello world". Поскольку строка не является объектом штатным объектом (только указатель) языка, она определяется вне тела функции. Комментарии начинаются с символа <strong>#</strong> и заканчиваются концом строки.<br />
<pre>Here is a complete "Hello World" IL file which defines a function that prints to the screen. Since the string is not a first class object (only the pointer is) it is defined outside the function's body. Comments start with a # character and finish with the end of the line.</pre><br />
<br />
# Объявление константной строки "hello world"<br />
data $str = { b "hello world", b 0 }<br />
<br />
function w $main() {<br />
@start<br />
# Вызов функции puts с аргументом $str.<br />
%r =w call $puts(l $str)<br />
ret 0<br />
}<br />
<br />
Если вы прочитали ссылку про язык [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM], вы можете понять вышеприведенный код. В сравнении, QBE предоставляет гораздо более простое использование типов и синтаксиса.<br />
<pre>If you have read the LLVM language reference, you might recognize the example above. In comparison, QBE makes a much lighter use of types and the syntax is terser.</pre><br />
<br />
== Запись БНФ == <br />
<br />
Синтаксис языка, который Вы сможете найти в разделах данной Wiki (и в оригинальной документации), описан с использованием [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ]. Различные используемые конструкции [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] перечислены ниже.<br />
<br />
Ключевые слова заключены в кавычки;<br />
... | ... выражает дизъюнкции;<br />
[ ... ] обозначает некоторый синтаксис как необязательный;<br />
( ... ), обозначает разделенный запятыми список прилагаемого синтаксиса;<br />
...* и ...+ используются для произвольных обозначений и для повторений соответственно.<br />
<br />
== Символы ==<br />
<br />
Промежуточный язык изобилует разными символами, все пользовательские имена выделяются символьным префиксом. Это делается для предотвращения конфликтов ключевых слов, а также для быстрого определения области видимости и характера идентификаторов.<br />
<pre>The intermediate language makes heavy use of sigils, all user-defined names are prefixed with a sigil. This is to avoid keyword conflicts, and also to quickly spot the scope and nature of identifiers.</pre><br />
<br />
<code>:</code> используется для определенных пользователем [[Составные типы данных | составных типов данных]]<br />
<code>$</code> используется для глобальных переменных (представленных в виде указателя)<br />
<code>%</code> используется для переменных внутри [[Функции | функций]]<br />
<code>@</code> используется для обозначения меток [[Блоки | блоков]]<br />
<br />
В этом синтаксисе [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] мы используем <code>?IDENT</code> для обозначения идентификатора, начинающегося с символа <code>?</code>.<br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Basic-Concepts c9x.me]<br />
<br />
== Сравнение с LLVM ==<br />
QBE и LLVM являются компиляторами, использующими представление SSA. В этом документе объясняется, почему LLVM не делает QBE лишним. Очевидно, что все следующее предвзято, потому что написано мной (разработчиком).<br />
<pre>Both QBE and LLVM are compiler backends using an SSA representation. This document will explain why LLVM does not make QBE a redundant project. Obviously, everything following is biased, because written by me.</pre><br />
<br />
==== Объем ====<br />
<br />
QBE - проект гораздо меньшего масштаба с разными целями, чем LLVM.<br />
<pre>QBE is a much smaller scale project with different goals than LLVM.</pre><br />
*QBE предназначен для разработчиков своего языка.<br />
<pre>QBE is for amateur language designers.</pre><br />
<br />
Он не затрагивает все проблемы, возникающие при разработке языка технического уровня. Если вы "играете" с некоторыми языками, использование LLVM будет походить на таскание вашего рюкзака с грузовиком, а использование QBE будет больше похоже на катание на велосипеде.<br />
<pre>It does not address all the problems faced when conceiving an industry-grade language. If you are toying with some language ideas, using LLVM will be like hauling your backpack with a truck, but using QBE will feel more like riding a bicycle.</pre<br />
<br />
*QBE - это первые 70%, а не последние 30%.<br />
<pre>QBE is about the first 70%, not the last 30%.</pre><br />
<br />
QBE пытается точно определить в многочисленной литературе о компиляции те оптимизации, которые дают вам 70% производительности в 10% кода в полномасштабных компиляторах.<br />
<pre>It attempts to pinpoint, in the extremely vast compilation literature, the optimizations that get you 70% of the performance in 10% of the code of full blown compilers.</pre<br />
Например, перевод в форму [https://ru.wikipedia.org/wiki/SSA SSA] реализован в 160 строках кода в QBE!<br />
<pre>For example, copy propagation on SSA form is implemented in 160 lines of code in QBE!</pre><br />
<br />
*QBE чрезвычайно открыт, прост и удобен в изучении.<br />
<pre>QBE is extremely hackable.</pre><br />
<br />
Во-первых, QBE есть и останется небольшим проектом (менее 8 KLOC, прим. 1 KLOCK (Kilo Lines Of Code) = 1000 строк кода.). Во-вторых, он реализован на непривлекательном C99 без каких-либо зависимостей. В-третьих, он может переводить в промежуточный язык и отлаживать информацию в едином формате после каждого прохода.<br />
<pre>First, it is, and will remain, a small project (less than 8 kloc). Second, it is programmed in non-fancy C99 without any dependencies. Third, it is able to dump the IL and debug information in a uniform format after each pass.</pre><br />
<br />
==== Особенности ====<br />
LLVM определенно более изобилует функциями, но в QBE есть интересных несколько вещей.<br />
<pre>LLVM is definitely more packed with features, but there are a few things provided in QBE to consider.</pre><br />
<br />
*LLVM НЕ обеспечивает вам полную совместимость с Си.<br />
<pre>LLVM does NOT provide full C compatibility for you.</pre><br />
<br />
В более технических терминах любой язык, который обеспечивает хорошую совместимость с Си и использует [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] в качестве платформы, должен переопределять большие куски [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] в своем интерфейсе! Эта хорошо известная проблема в сообществе [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] вызывает много дублирования и ошибок. Реализация готового Си [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] (с аргументами структуры и возвратами) невероятно сложна, и не слишком весела. QBE предоставляет вам операции промежуточного языка для вызова (и вызывается с) без лишних проблем. Кроме того, реализация [https://ru.wikipedia.org/wiki/Двоичный_интерфейс_приложений ABI] в QBE была тщательно протестирована путем испытаний вручную.<br />
<pre>In more technical terms, any language that provides good C compatibility and uses LLVM as a backend needs to reimplement large chunks of the ABI in its frontend! This well known issue in the LLVM community causes a great deal of duplication and bugs. Implementing a complete C ABI (with struct arguments and returns) is incredibly tricky, and not really a lot of fun. QBE provides you with IL operations to call in (and be called by) C with no pain. Moreover the ABI implementation in QBE has been thoroughly tested by fuzzing and manual tests.</pre><br />
<br />
*LLVM IL более загроможден операциями памяти.<br />
<pre>LLVM IL is more cluttered with memory operations.</pre><br />
<br />
Реализация конструкции [https://ru.wikipedia.org/wiki/SSA SSA] сложна. Чтобы уберечь своих пользователей от необходимости его реализации, [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] предоставляет части стека. Это означает, что одно увеличение на 1 переменной <code>v</code> будет состоять из трех инструкций [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM]: одна выгрузка, одно добавление и одно сохранение. QBE предоставляет простые типы переменных, отличные от [https://ru.wikipedia.org/wiki/SSA SSA], поэтому увеличение <code>v</code> выполняется просто с помощью одной команды <code>%v = w add% v, 1</code>. Это может показаться визуальным преимуществом, но увеличение количества команд из одной до трех упрощает для разработчиков выявление ошибок в сгенерированном коде.<br />
<pre>Implementing SSA construction is hard. To save its users from having to implement it, LLVM provides stack slots. This means that one increment of a variable v will be composed of three LLVM instructions: one load, one add, and one store. QBE provides simple non-SSA temporaries, so incrementing v is simply done with one instruction %v =w add %v, 1. This could seem cosmetic, but dividing the size of the IL by three makes it easier for the frontend writers to spot bugs in the generated code.</pre><br />
<br />
*LLVM IL более загроможден с объявлениями и преобразованиями типов.<br />
<pre>LLVM IL is more cluttered with type annotations and casts.</pre><br />
<br />
Для улучшения оптимизации и корректности [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM] имеет сложные типы промежуточного представления. Тем не менее, только несколько типов действительно являются первоклассными, и многие операции с исходными языками требуют компиляции списков. Поскольку QBE реализует гораздо более простое использование типов, промежуточное представление более читабельно и короче. Разумеется, можно утверждать, что достоинства QBE не столь велики, но помните, что на практике большое количество преобразований, необходимых в ILL LLVM, подрывает общую эффективность системы типов.<br />
<pre>For the sake of advanced optimizations and correctness, LLVM has complex IL types. However, only a few types are really first class and many operations of source languages require casts to be compiled. Because QBE makes a much lighter use of types, the IL is more readable and shorter. It can of course be argued back that the correctness of QBE is jeoparadized, but remember that, in practice, the large amount of casts necessary in LLVM IL is undermining the overall effectiveness of the type system.</pre></div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=58Заглавная страница2018-03-20T12:12:39Z<p>Admin: </p>
<hr />
<div>Приветствую на главной странице прототипа Wiki по QBE IL, разрабатываемого в рамках группового проекта для курса "Конструирование компиляторов", читаемого на факультете [https://ru.wikipedia.org/wiki/Факультет_вычислительной_математики_и_кибернетики_МГУ Вычислительной математики и кибернетики МГУ имени М.В. Ломоносова].<br />
<br />
Верхний лист (точка входа) дерева данной Wiki - вводная статья о самом [[QBE]]<br />
<br />
Позднее, на данной странице появится категоризированное оглавление всего содержимого Wiki.<br />
<br />
Общий план проекта:<br />
<br />
# [[QBE]] будет содержать общее описание языка;<br><br />
# Описание языка. Под этим подразумевается русификация и разбиения на отдельные страницы имеющейся документации c9x.me/compile/;<br><br />
# Отдельными страницами планируется описать неофициальный Си-интерфейс, с описанием и разбором содержимого его файлов;<br><br />
# [[Примеры кода QBE IL]];<br><br />
# Различные проблемы, которые могут возникнуть при написании программ на языке QBE, либо с использованием Си библиотеки;<br><br />
# Некоторые теоретические части из лекций.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BA%D0%BE%D0%B4%D0%B0_QBE_IL&diff=57Примеры кода QBE IL2018-03-20T12:03:31Z<p>Admin: </p>
<hr />
<div><strong>ВАЖНО!</strong> Пожалуйста, обратите внимание, некоторые операции, приведенные в примерах, используются без "левой части" (например, <code>%x = w ...</code>). Это не ошибка, примеры имеют такой вид исключительно ради наглядности и конкретизации тем, обозначенных в заголовках примеров.<br />
<br />
== Операции и операнды ==<br />
Рассмотрим некоторые операции и операнды в [[QBE]].<br />
<br />
Подробнее можно прочитать в разделе [[Арифметические и битовые операции]].<br />
Обычная арифметика - сложение (add), вычитание (sub), деление (div), умножение (mul). Каждая из этих операций требует два аргумента/операнда (очевидно). <br />
<br />
Примеры.<br />
<br />
add 0, 1 <br />
К нулю (первое слагаемое/первый аргумент/операнд) прибавляется единица (второе слагаемое/второй аргумент/операнд). Результатом сложения (сумма) будет число 1.<br />
<br />
sub 2, 1<br />
Из двойки (уменьшаемое/первый аргумент/операнд) вычитается единица (вычитаемое/второй аргумент/операнд). Результатом вычитания (разностью) будет число 1.<br />
<br />
div 4, 2<br />
Четыре (делимое/первый аргумент/операнд) делится на два (делитель/второй аргумент/операнд). Результатом деления (частным) будет число 2.<br />
<br />
mul 2, 2<br />
Два (первый множитель/первый аргумент/операнд) умножается на два (второй множитель/второй аргумент/операнд). Результатом умножения (произведением) будет число 4.<br />
<br />
Аналогично для логических операций.<br />
Для операций сдвига справедливо требование наличие двух аргументов/операндов. В этом случае первый аргумент/операнд будет являться тем, что требуется "сдвинуть", а второй – числом (целым), на которое требуется осуществить сдвиг.<br />
<br />
Операции над [[Память | памятью]].<br />
<br />
Основные операции для работы с памятью, которые могут понадобиться Вам для взаимодействия с массивами данных – <code>store</code> и <code>load</code>. Особенности применения описаны в соответствующей статье, как на данном ресурсе, так и в [https://c9x.me/compile/ оригинальной документации]. Приведем пример использования этих команд.<br />
<br />
storeb 0, %array<br />
Разместит в первый байт массива <code>array</code> (то есть <code>%array</code> выступает аналогом <code>array[0]</code>) число 0. Суффикс <code>b</code> на конце инструкции <code>store</code> свидетельствует о типе используемых операндов.<br />
<br />
loadub %array<br />
Результатом выполнения инструкции будет усеченное до unsigned (беззнаковое) значение первого байта массива <code>array</code>. Суффиксы <code>u</code> и <code>b</code> означают unsigned (беззнаковое) и byte (байт) соответственно. То есть суффиксы инструкции <code>load</code> накладывают ограничение на возвращаемый результат.<br />
<br />
Подробнее о работе с массивами будет рассказано ниже.<br />
<br />
== Присваивания ==<br />
<br />
Пример кода на Си.<br />
int a = 1;<br />
int b = 2;<br />
int c;<br />
c = a + b;<br />
<br />
Аналогичный код на QBE IL.<br />
%a = w add 0, 1<br />
%b = w add 0, 2<br />
%c = w add %a, %b<br />
<br />
== Блоки ==<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
Результатом выполнения будет <code> c = 3 </code>, а без наличия переходов между блоками каждая инструкция будет выполняться последовательно. То есть в блоке <code>@start</code> в переменную <code>b</code> будет помещено число 5. Затем мы попадем в блок <code>@initA</code>, где объявим переменную <code>a</code> и положим в нее число 1. Далее, в блоке <code>@initB</code> уже размещенное в переменной <code>b</code> будет заменено на число 2. В блоке <code>@result</code> объявляется переменная <code>c</code> и инициализируется суммой переменных <code>a</code> и <code>b</code>, эта сумма будет равна 3 (1+2). Блок <code>@end</code> осуществит выход из функции.<br />
<br />
== Сравнения ==<br />
<br />
Вы можете найти более подробную информацию в разделе [[Сравнения]]. Все сравнения, реализованные в [[QBE | промежуточном языке]] практически идентичны сравнениям в языке ассемблера. Главным образом, сравнения применяются для осуществления управления условными переходами (представлено ниже). В [[QBE | промежуточном языке]] представлено несколько видов сравнения для разных типов данных: сравнение на равенство аргументов/операндов, сравнение на неравенство аргументов/операндов, сравнение на "больше или равно", сравнение на "меньше или равно", сравнение на "меньше", сравнение на "больше".<br />
<br />
%condition = w cslew %a, %b<br />
Данный пример сравнивает две переменных размерности w (word) (о чем свидетельствует окончание инструкции - <code>w</code>) на "меньше или равно" (суффикс <code>le</code> означает "lower or equal") и возвращает 0 размерности w (word) в случае, если <code>%b</code> больше <code>%a</code>, либо 1 размерности w (word) в случае положительного выполнения условий суффикса. <br />
<br />
<br />
<br />
== Переходы ==<br />
<br />
Рассмотрим код из предыдущего примера с "Блоками", но внесем одно изменение – установим безусловный переход <code>jmp</code> на другой блок в блоке <code>@initA</code>. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
jmp @result<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
При выполнении, с помощью <code>jmp @result</code> после объявления переменной <code>a</code> выполнение продолжится не последовательно (в блоке <code>@initB</code>), а с блока <code>@result</code>. То есть <code>c = 1 + 5</code> (не произойдет переприсваивания <code>b = 2</code>), тем самым, результатом в <code>c</code> будет являться число 6.<br />
<br />
Заменим безусловный переход <code>jmp @result</code> из примера выше на переход по условию <code>%condition</code>, которое добавим перед переходом. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
%condition = w cslew %a, 2<br />
jnz %condition, @result, @initB<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
В данном случае, условие <code>%condition = w cslew %a, 2</code> всегда будет выполняться, а переход <code>jnz %condition, @result, @initB</code> всегда будет переходить на ветвь <code>@result</code>. Но если сравнение, например, в <code>@initA</code> в переменную <code>%a</code> положить не 1, а 3, то условие будет всегда ложным, тогда переход будет всегда выполняться на ветвь <code>@initB</code>, и результатом выполнения программы будет <code>%c = 3 (т.к. a = 3) + 2 (т.к. в b будет лежать 2) = 5</code><br />
<br />
== Массивы ==<br />
<br />
Предположим, у нас имеется массив байтов <code>array</code> неопределенного размера и некоторое целое беззнаковое число N. Для работы с N-ным элементом массива придется завести дополнительную переменную (дабы не утратить указатель на первые N элементов), в которой будет размещена сумма адреса первого элемента массива и сдвига на N байт.<br />
%arrayN = l add %array, %N<br />
Теперь с помощью <code>arrayN</code> и инструкций <code>load</code> и <code>store</code> можно получить и записать (соответственно) в N-ный элемент массива <code>array</code>.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BA%D0%BE%D0%B4%D0%B0_QBE_IL&diff=56Примеры кода QBE IL2018-03-20T12:03:20Z<p>Admin: </p>
<hr />
<div><strong>ВАЖНО!</strong> Пожалуйста, обратите внимание, некоторые операции, приведенные в примерах, используются без "левой части" (например, <code>%x = w ...</code>. Это не ошибка, примеры имеют такой вид исключительно ради наглядности и конкретизации тем, обозначенных в заголовках примеров.<br />
<br />
== Операции и операнды ==<br />
Рассмотрим некоторые операции и операнды в [[QBE]].<br />
<br />
Подробнее можно прочитать в разделе [[Арифметические и битовые операции]].<br />
Обычная арифметика - сложение (add), вычитание (sub), деление (div), умножение (mul). Каждая из этих операций требует два аргумента/операнда (очевидно). <br />
<br />
Примеры.<br />
<br />
add 0, 1 <br />
К нулю (первое слагаемое/первый аргумент/операнд) прибавляется единица (второе слагаемое/второй аргумент/операнд). Результатом сложения (сумма) будет число 1.<br />
<br />
sub 2, 1<br />
Из двойки (уменьшаемое/первый аргумент/операнд) вычитается единица (вычитаемое/второй аргумент/операнд). Результатом вычитания (разностью) будет число 1.<br />
<br />
div 4, 2<br />
Четыре (делимое/первый аргумент/операнд) делится на два (делитель/второй аргумент/операнд). Результатом деления (частным) будет число 2.<br />
<br />
mul 2, 2<br />
Два (первый множитель/первый аргумент/операнд) умножается на два (второй множитель/второй аргумент/операнд). Результатом умножения (произведением) будет число 4.<br />
<br />
Аналогично для логических операций.<br />
Для операций сдвига справедливо требование наличие двух аргументов/операндов. В этом случае первый аргумент/операнд будет являться тем, что требуется "сдвинуть", а второй – числом (целым), на которое требуется осуществить сдвиг.<br />
<br />
Операции над [[Память | памятью]].<br />
<br />
Основные операции для работы с памятью, которые могут понадобиться Вам для взаимодействия с массивами данных – <code>store</code> и <code>load</code>. Особенности применения описаны в соответствующей статье, как на данном ресурсе, так и в [https://c9x.me/compile/ оригинальной документации]. Приведем пример использования этих команд.<br />
<br />
storeb 0, %array<br />
Разместит в первый байт массива <code>array</code> (то есть <code>%array</code> выступает аналогом <code>array[0]</code>) число 0. Суффикс <code>b</code> на конце инструкции <code>store</code> свидетельствует о типе используемых операндов.<br />
<br />
loadub %array<br />
Результатом выполнения инструкции будет усеченное до unsigned (беззнаковое) значение первого байта массива <code>array</code>. Суффиксы <code>u</code> и <code>b</code> означают unsigned (беззнаковое) и byte (байт) соответственно. То есть суффиксы инструкции <code>load</code> накладывают ограничение на возвращаемый результат.<br />
<br />
Подробнее о работе с массивами будет рассказано ниже.<br />
<br />
== Присваивания ==<br />
<br />
Пример кода на Си.<br />
int a = 1;<br />
int b = 2;<br />
int c;<br />
c = a + b;<br />
<br />
Аналогичный код на QBE IL.<br />
%a = w add 0, 1<br />
%b = w add 0, 2<br />
%c = w add %a, %b<br />
<br />
== Блоки ==<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
Результатом выполнения будет <code> c = 3 </code>, а без наличия переходов между блоками каждая инструкция будет выполняться последовательно. То есть в блоке <code>@start</code> в переменную <code>b</code> будет помещено число 5. Затем мы попадем в блок <code>@initA</code>, где объявим переменную <code>a</code> и положим в нее число 1. Далее, в блоке <code>@initB</code> уже размещенное в переменной <code>b</code> будет заменено на число 2. В блоке <code>@result</code> объявляется переменная <code>c</code> и инициализируется суммой переменных <code>a</code> и <code>b</code>, эта сумма будет равна 3 (1+2). Блок <code>@end</code> осуществит выход из функции.<br />
<br />
== Сравнения ==<br />
<br />
Вы можете найти более подробную информацию в разделе [[Сравнения]]. Все сравнения, реализованные в [[QBE | промежуточном языке]] практически идентичны сравнениям в языке ассемблера. Главным образом, сравнения применяются для осуществления управления условными переходами (представлено ниже). В [[QBE | промежуточном языке]] представлено несколько видов сравнения для разных типов данных: сравнение на равенство аргументов/операндов, сравнение на неравенство аргументов/операндов, сравнение на "больше или равно", сравнение на "меньше или равно", сравнение на "меньше", сравнение на "больше".<br />
<br />
%condition = w cslew %a, %b<br />
Данный пример сравнивает две переменных размерности w (word) (о чем свидетельствует окончание инструкции - <code>w</code>) на "меньше или равно" (суффикс <code>le</code> означает "lower or equal") и возвращает 0 размерности w (word) в случае, если <code>%b</code> больше <code>%a</code>, либо 1 размерности w (word) в случае положительного выполнения условий суффикса. <br />
<br />
<br />
<br />
== Переходы ==<br />
<br />
Рассмотрим код из предыдущего примера с "Блоками", но внесем одно изменение – установим безусловный переход <code>jmp</code> на другой блок в блоке <code>@initA</code>. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
jmp @result<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
При выполнении, с помощью <code>jmp @result</code> после объявления переменной <code>a</code> выполнение продолжится не последовательно (в блоке <code>@initB</code>), а с блока <code>@result</code>. То есть <code>c = 1 + 5</code> (не произойдет переприсваивания <code>b = 2</code>), тем самым, результатом в <code>c</code> будет являться число 6.<br />
<br />
Заменим безусловный переход <code>jmp @result</code> из примера выше на переход по условию <code>%condition</code>, которое добавим перед переходом. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
%condition = w cslew %a, 2<br />
jnz %condition, @result, @initB<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
В данном случае, условие <code>%condition = w cslew %a, 2</code> всегда будет выполняться, а переход <code>jnz %condition, @result, @initB</code> всегда будет переходить на ветвь <code>@result</code>. Но если сравнение, например, в <code>@initA</code> в переменную <code>%a</code> положить не 1, а 3, то условие будет всегда ложным, тогда переход будет всегда выполняться на ветвь <code>@initB</code>, и результатом выполнения программы будет <code>%c = 3 (т.к. a = 3) + 2 (т.к. в b будет лежать 2) = 5</code><br />
<br />
== Массивы ==<br />
<br />
Предположим, у нас имеется массив байтов <code>array</code> неопределенного размера и некоторое целое беззнаковое число N. Для работы с N-ным элементом массива придется завести дополнительную переменную (дабы не утратить указатель на первые N элементов), в которой будет размещена сумма адреса первого элемента массива и сдвига на N байт.<br />
%arrayN = l add %array, %N<br />
Теперь с помощью <code>arrayN</code> и инструкций <code>load</code> и <code>store</code> можно получить и записать (соответственно) в N-ный элемент массива <code>array</code>.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BA%D0%BE%D0%B4%D0%B0_QBE_IL&diff=55Примеры кода QBE IL2018-03-20T12:02:42Z<p>Admin: </p>
<hr />
<div><strong>ВАЖНО!</strong> Пожалуйста, обратите внимание, некоторые операции, приведенные в примерах, используются без "левой части". Это не ошибка, примеры имеют такой вид исключительно ради наглядности и конкретизации тем, обозначенных в заголовках примеров.<br />
<br />
== Операции и операнды ==<br />
Рассмотрим некоторые операции и операнды в [[QBE]].<br />
<br />
Подробнее можно прочитать в разделе [[Арифметические и битовые операции]].<br />
Обычная арифметика - сложение (add), вычитание (sub), деление (div), умножение (mul). Каждая из этих операций требует два аргумента/операнда (очевидно). <br />
<br />
Примеры.<br />
<br />
add 0, 1 <br />
К нулю (первое слагаемое/первый аргумент/операнд) прибавляется единица (второе слагаемое/второй аргумент/операнд). Результатом сложения (сумма) будет число 1.<br />
<br />
sub 2, 1<br />
Из двойки (уменьшаемое/первый аргумент/операнд) вычитается единица (вычитаемое/второй аргумент/операнд). Результатом вычитания (разностью) будет число 1.<br />
<br />
div 4, 2<br />
Четыре (делимое/первый аргумент/операнд) делится на два (делитель/второй аргумент/операнд). Результатом деления (частным) будет число 2.<br />
<br />
mul 2, 2<br />
Два (первый множитель/первый аргумент/операнд) умножается на два (второй множитель/второй аргумент/операнд). Результатом умножения (произведением) будет число 4.<br />
<br />
Аналогично для логических операций.<br />
Для операций сдвига справедливо требование наличие двух аргументов/операндов. В этом случае первый аргумент/операнд будет являться тем, что требуется "сдвинуть", а второй – числом (целым), на которое требуется осуществить сдвиг.<br />
<br />
Операции над [[Память | памятью]].<br />
<br />
Основные операции для работы с памятью, которые могут понадобиться Вам для взаимодействия с массивами данных – <code>store</code> и <code>load</code>. Особенности применения описаны в соответствующей статье, как на данном ресурсе, так и в [https://c9x.me/compile/ оригинальной документации]. Приведем пример использования этих команд.<br />
<br />
storeb 0, %array<br />
Разместит в первый байт массива <code>array</code> (то есть <code>%array</code> выступает аналогом <code>array[0]</code>) число 0. Суффикс <code>b</code> на конце инструкции <code>store</code> свидетельствует о типе используемых операндов.<br />
<br />
loadub %array<br />
Результатом выполнения инструкции будет усеченное до unsigned (беззнаковое) значение первого байта массива <code>array</code>. Суффиксы <code>u</code> и <code>b</code> означают unsigned (беззнаковое) и byte (байт) соответственно. То есть суффиксы инструкции <code>load</code> накладывают ограничение на возвращаемый результат.<br />
<br />
Подробнее о работе с массивами будет рассказано ниже.<br />
<br />
== Присваивания ==<br />
<br />
Пример кода на Си.<br />
int a = 1;<br />
int b = 2;<br />
int c;<br />
c = a + b;<br />
<br />
Аналогичный код на QBE IL.<br />
%a = w add 0, 1<br />
%b = w add 0, 2<br />
%c = w add %a, %b<br />
<br />
== Блоки ==<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
Результатом выполнения будет <code> c = 3 </code>, а без наличия переходов между блоками каждая инструкция будет выполняться последовательно. То есть в блоке <code>@start</code> в переменную <code>b</code> будет помещено число 5. Затем мы попадем в блок <code>@initA</code>, где объявим переменную <code>a</code> и положим в нее число 1. Далее, в блоке <code>@initB</code> уже размещенное в переменной <code>b</code> будет заменено на число 2. В блоке <code>@result</code> объявляется переменная <code>c</code> и инициализируется суммой переменных <code>a</code> и <code>b</code>, эта сумма будет равна 3 (1+2). Блок <code>@end</code> осуществит выход из функции.<br />
<br />
== Сравнения ==<br />
<br />
Вы можете найти более подробную информацию в разделе [[Сравнения]]. Все сравнения, реализованные в [[QBE | промежуточном языке]] практически идентичны сравнениям в языке ассемблера. Главным образом, сравнения применяются для осуществления управления условными переходами (представлено ниже). В [[QBE | промежуточном языке]] представлено несколько видов сравнения для разных типов данных: сравнение на равенство аргументов/операндов, сравнение на неравенство аргументов/операндов, сравнение на "больше или равно", сравнение на "меньше или равно", сравнение на "меньше", сравнение на "больше".<br />
<br />
%condition = w cslew %a, %b<br />
Данный пример сравнивает две переменных размерности w (word) (о чем свидетельствует окончание инструкции - <code>w</code>) на "меньше или равно" (суффикс <code>le</code> означает "lower or equal") и возвращает 0 размерности w (word) в случае, если <code>%b</code> больше <code>%a</code>, либо 1 размерности w (word) в случае положительного выполнения условий суффикса. <br />
<br />
<br />
<br />
== Переходы ==<br />
<br />
Рассмотрим код из предыдущего примера с "Блоками", но внесем одно изменение – установим безусловный переход <code>jmp</code> на другой блок в блоке <code>@initA</code>. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
jmp @result<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
При выполнении, с помощью <code>jmp @result</code> после объявления переменной <code>a</code> выполнение продолжится не последовательно (в блоке <code>@initB</code>), а с блока <code>@result</code>. То есть <code>c = 1 + 5</code> (не произойдет переприсваивания <code>b = 2</code>), тем самым, результатом в <code>c</code> будет являться число 6.<br />
<br />
Заменим безусловный переход <code>jmp @result</code> из примера выше на переход по условию <code>%condition</code>, которое добавим перед переходом. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
%condition = w cslew %a, 2<br />
jnz %condition, @result, @initB<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
В данном случае, условие <code>%condition = w cslew %a, 2</code> всегда будет выполняться, а переход <code>jnz %condition, @result, @initB</code> всегда будет переходить на ветвь <code>@result</code>. Но если сравнение, например, в <code>@initA</code> в переменную <code>%a</code> положить не 1, а 3, то условие будет всегда ложным, тогда переход будет всегда выполняться на ветвь <code>@initB</code>, и результатом выполнения программы будет <code>%c = 3 (т.к. a = 3) + 2 (т.к. в b будет лежать 2) = 5</code><br />
<br />
== Массивы ==<br />
<br />
Предположим, у нас имеется массив байтов <code>array</code> неопределенного размера и некоторое целое беззнаковое число N. Для работы с N-ным элементом массива придется завести дополнительную переменную (дабы не утратить указатель на первые N элементов), в которой будет размещена сумма адреса первого элемента массива и сдвига на N байт.<br />
%arrayN = l add %array, %N<br />
Теперь с помощью <code>arrayN</code> и инструкций <code>load</code> и <code>store</code> можно получить и записать (соответственно) в N-ный элемент массива <code>array</code>.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BA%D0%BE%D0%B4%D0%B0_QBE_IL&diff=54Примеры кода QBE IL2018-03-20T12:02:14Z<p>Admin: </p>
<hr />
<div>Пожалуйста, обратите внимание, некоторые операции, приведенные в примерах, используются без "левой части". Это не ошибка, примеры имеют такой вид исключительно ради наглядности и конкретизации тем, обозначенных в заголовках примеров.<br />
<br />
== Операции и операнды ==<br />
Рассмотрим некоторые операции и операнды в [[QBE]].<br />
<br />
Подробнее можно прочитать в разделе [[Арифметические и битовые операции]].<br />
Обычная арифметика - сложение (add), вычитание (sub), деление (div), умножение (mul). Каждая из этих операций требует два аргумента/операнда (очевидно). <br />
<br />
Примеры.<br />
<br />
add 0, 1 <br />
К нулю (первое слагаемое/первый аргумент/операнд) прибавляется единица (второе слагаемое/второй аргумент/операнд). Результатом сложения (сумма) будет число 1.<br />
<br />
sub 2, 1<br />
Из двойки (уменьшаемое/первый аргумент/операнд) вычитается единица (вычитаемое/второй аргумент/операнд). Результатом вычитания (разностью) будет число 1.<br />
<br />
div 4, 2<br />
Четыре (делимое/первый аргумент/операнд) делится на два (делитель/второй аргумент/операнд). Результатом деления (частным) будет число 2.<br />
<br />
mul 2, 2<br />
Два (первый множитель/первый аргумент/операнд) умножается на два (второй множитель/второй аргумент/операнд). Результатом умножения (произведением) будет число 4.<br />
<br />
Аналогично для логических операций.<br />
Для операций сдвига справедливо требование наличие двух аргументов/операндов. В этом случае первый аргумент/операнд будет являться тем, что требуется "сдвинуть", а второй – числом (целым), на которое требуется осуществить сдвиг.<br />
<br />
Операции над [[Память | памятью]].<br />
<br />
Основные операции для работы с памятью, которые могут понадобиться Вам для взаимодействия с массивами данных – <code>store</code> и <code>load</code>. Особенности применения описаны в соответствующей статье, как на данном ресурсе, так и в [https://c9x.me/compile/ оригинальной документации]. Приведем пример использования этих команд.<br />
<br />
storeb 0, %array<br />
Разместит в первый байт массива <code>array</code> (то есть <code>%array</code> выступает аналогом <code>array[0]</code>) число 0. Суффикс <code>b</code> на конце инструкции <code>store</code> свидетельствует о типе используемых операндов.<br />
<br />
loadub %array<br />
Результатом выполнения инструкции будет усеченное до unsigned (беззнаковое) значение первого байта массива <code>array</code>. Суффиксы <code>u</code> и <code>b</code> означают unsigned (беззнаковое) и byte (байт) соответственно. То есть суффиксы инструкции <code>load</code> накладывают ограничение на возвращаемый результат.<br />
<br />
Подробнее о работе с массивами будет рассказано ниже.<br />
<br />
== Присваивания ==<br />
<br />
Пример кода на Си.<br />
int a = 1;<br />
int b = 2;<br />
int c;<br />
c = a + b;<br />
<br />
Аналогичный код на QBE IL.<br />
%a = w add 0, 1<br />
%b = w add 0, 2<br />
%c = w add %a, %b<br />
<br />
== Блоки ==<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
Результатом выполнения будет <code> c = 3 </code>, а без наличия переходов между блоками каждая инструкция будет выполняться последовательно. То есть в блоке <code>@start</code> в переменную <code>b</code> будет помещено число 5. Затем мы попадем в блок <code>@initA</code>, где объявим переменную <code>a</code> и положим в нее число 1. Далее, в блоке <code>@initB</code> уже размещенное в переменной <code>b</code> будет заменено на число 2. В блоке <code>@result</code> объявляется переменная <code>c</code> и инициализируется суммой переменных <code>a</code> и <code>b</code>, эта сумма будет равна 3 (1+2). Блок <code>@end</code> осуществит выход из функции.<br />
<br />
== Сравнения ==<br />
<br />
Вы можете найти более подробную информацию в разделе [[Сравнения]]. Все сравнения, реализованные в [[QBE | промежуточном языке]] практически идентичны сравнениям в языке ассемблера. Главным образом, сравнения применяются для осуществления управления условными переходами (представлено ниже). В [[QBE | промежуточном языке]] представлено несколько видов сравнения для разных типов данных: сравнение на равенство аргументов/операндов, сравнение на неравенство аргументов/операндов, сравнение на "больше или равно", сравнение на "меньше или равно", сравнение на "меньше", сравнение на "больше".<br />
<br />
%condition = w cslew %a, %b<br />
Данный пример сравнивает две переменных размерности w (word) (о чем свидетельствует окончание инструкции - <code>w</code>) на "меньше или равно" (суффикс <code>le</code> означает "lower or equal") и возвращает 0 размерности w (word) в случае, если <code>%b</code> больше <code>%a</code>, либо 1 размерности w (word) в случае положительного выполнения условий суффикса. <br />
<br />
<br />
<br />
== Переходы ==<br />
<br />
Рассмотрим код из предыдущего примера с "Блоками", но внесем одно изменение – установим безусловный переход <code>jmp</code> на другой блок в блоке <code>@initA</code>. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
jmp @result<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
При выполнении, с помощью <code>jmp @result</code> после объявления переменной <code>a</code> выполнение продолжится не последовательно (в блоке <code>@initB</code>), а с блока <code>@result</code>. То есть <code>c = 1 + 5</code> (не произойдет переприсваивания <code>b = 2</code>), тем самым, результатом в <code>c</code> будет являться число 6.<br />
<br />
Заменим безусловный переход <code>jmp @result</code> из примера выше на переход по условию <code>%condition</code>, которое добавим перед переходом. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
%condition = w cslew %a, 2<br />
jnz %condition, @result, @initB<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
В данном случае, условие <code>%condition = w cslew %a, 2</code> всегда будет выполняться, а переход <code>jnz %condition, @result, @initB</code> всегда будет переходить на ветвь <code>@result</code>. Но если сравнение, например, в <code>@initA</code> в переменную <code>%a</code> положить не 1, а 3, то условие будет всегда ложным, тогда переход будет всегда выполняться на ветвь <code>@initB</code>, и результатом выполнения программы будет <code>%c = 3 (т.к. a = 3) + 2 (т.к. в b будет лежать 2) = 5</code><br />
<br />
== Массивы ==<br />
<br />
Предположим, у нас имеется массив байтов <code>array</code> неопределенного размера и некоторое целое беззнаковое число N. Для работы с N-ным элементом массива придется завести дополнительную переменную (дабы не утратить указатель на первые N элементов), в которой будет размещена сумма адреса первого элемента массива и сдвига на N байт.<br />
%arrayN = l add %array, %N<br />
Теперь с помощью <code>arrayN</code> и инструкций <code>load</code> и <code>store</code> можно получить и записать (соответственно) в N-ный элемент массива <code>array</code>.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%BA%D0%BE%D0%B4%D0%B0_QBE_IL&diff=53Примеры кода QBE IL2018-03-19T17:25:15Z<p>Admin: Новая страница: «== Операции и операнды == Рассмотрим некоторые операции и операнды в QBE. Подробнее можно…»</p>
<hr />
<div>== Операции и операнды ==<br />
Рассмотрим некоторые операции и операнды в [[QBE]].<br />
<br />
Подробнее можно прочитать в разделе [[Арифметические и битовые операции]].<br />
Обычная арифметика - сложение (add), вычитание (sub), деление (div), умножение (mul). Каждая из этих операций требует два аргумента/операнда (очевидно). <br />
<br />
Примеры.<br />
<br />
add 0, 1 <br />
К нулю (первое слагаемое/первый аргумент/операнд) прибавляется единица (второе слагаемое/второй аргумент/операнд). Результатом сложения (сумма) будет число 1.<br />
<br />
sub 2, 1<br />
Из двойки (уменьшаемое/первый аргумент/операнд) вычитается единица (вычитаемое/второй аргумент/операнд). Результатом вычитания (разностью) будет число 1.<br />
<br />
div 4, 2<br />
Четыре (делимое/первый аргумент/операнд) делится на два (делитель/второй аргумент/операнд). Результатом деления (частным) будет число 2.<br />
<br />
mul 2, 2<br />
Два (первый множитель/первый аргумент/операнд) умножается на два (второй множитель/второй аргумент/операнд). Результатом умножения (произведением) будет число 4.<br />
<br />
Аналогично для логических операций.<br />
Для операций сдвига справедливо требование наличие двух аргументов/операндов. В этом случае первый аргумент/операнд будет являться тем, что требуется "сдвинуть", а второй – числом (целым), на которое требуется осуществить сдвиг.<br />
<br />
Операции над [[Память | памятью]].<br />
<br />
Основные операции для работы с памятью, которые могут понадобиться Вам для взаимодействия с массивами данных – <code>store</code> и <code>load</code>. Особенности применения описаны в соответствующей статье, как на данном ресурсе, так и в [https://c9x.me/compile/ оригинальной документации]. Приведем пример использования этих команд.<br />
<br />
storeb 0, %array<br />
Разместит в первый байт массива <code>array</code> (то есть <code>%array</code> выступает аналогом <code>array[0]</code>) число 0. Суффикс <code>b</code> на конце инструкции <code>store</code> свидетельствует о типе используемых операндов.<br />
<br />
loadub %array<br />
Результатом выполнения инструкции будет усеченное до unsigned (беззнаковое) значение первого байта массива <code>array</code>. Суффиксы <code>u</code> и <code>b</code> означают unsigned (беззнаковое) и byte (байт) соответственно. То есть суффиксы инструкции <code>load</code> накладывают ограничение на возвращаемый результат.<br />
<br />
Подробнее о работе с массивами будет рассказано ниже.<br />
<br />
== Присваивания ==<br />
<br />
Пример кода на Си.<br />
int a = 1;<br />
int b = 2;<br />
int c;<br />
c = a + b;<br />
<br />
Аналогичный код на QBE IL.<br />
%a = w add 0, 1<br />
%b = w add 0, 2<br />
%c = w add %a, %b<br />
<br />
== Блоки ==<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
Результатом выполнения будет <code> c = 3 </code>, а без наличия переходов между блоками каждая инструкция будет выполняться последовательно. То есть в блоке <code>@start</code> в переменную <code>b</code> будет помещено число 5. Затем мы попадем в блок <code>@initA</code>, где объявим переменную <code>a</code> и положим в нее число 1. Далее, в блоке <code>@initB</code> уже размещенное в переменной <code>b</code> будет заменено на число 2. В блоке <code>@result</code> объявляется переменная <code>c</code> и инициализируется суммой переменных <code>a</code> и <code>b</code>, эта сумма будет равна 3 (1+2). Блок <code>@end</code> осуществит выход из функции.<br />
<br />
== Сравнения ==<br />
<br />
Вы можете найти более подробную информацию в разделе [[Сравнения]]. Все сравнения, реализованные в [[QBE | промежуточном языке]] практически идентичны сравнениям в языке ассемблера. Главным образом, сравнения применяются для осуществления управления условными переходами (представлено ниже). В [[QBE | промежуточном языке]] представлено несколько видов сравнения для разных типов данных: сравнение на равенство аргументов/операндов, сравнение на неравенство аргументов/операндов, сравнение на "больше или равно", сравнение на "меньше или равно", сравнение на "меньше", сравнение на "больше".<br />
<br />
%condition = w cslew %a, %b<br />
Данный пример сравнивает две переменных размерности w (word) (о чем свидетельствует окончание инструкции - <code>w</code>) на "меньше или равно" (суффикс <code>le</code> означает "lower or equal") и возвращает 0 размерности w (word) в случае, если <code>%b</code> больше <code>%a</code>, либо 1 размерности w (word) в случае положительного выполнения условий суффикса. <br />
<br />
<br />
<br />
== Переходы ==<br />
<br />
Рассмотрим код из предыдущего примера с "Блоками", но внесем одно изменение – установим безусловный переход <code>jmp</code> на другой блок в блоке <code>@initA</code>. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
jmp @result<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
При выполнении, с помощью <code>jmp @result</code> после объявления переменной <code>a</code> выполнение продолжится не последовательно (в блоке <code>@initB</code>), а с блока <code>@result</code>. То есть <code>c = 1 + 5</code> (не произойдет переприсваивания <code>b = 2</code>), тем самым, результатом в <code>c</code> будет являться число 6.<br />
<br />
Заменим безусловный переход <code>jmp @result</code> из примера выше на переход по условию <code>%condition</code>, которое добавим перед переходом. <br />
<br />
@start<br />
%b = w add 0, 5<br />
@initA<br />
%a = w add 0, 1<br />
%condition = w cslew %a, 2<br />
jnz %condition, @result, @initB<br />
@initB<br />
%b = w add 0, 2<br />
@result<br />
%c = w add %a, %b<br />
@end<br />
ret 0<br />
<br />
В данном случае, условие <code>%condition = w cslew %a, 2</code> всегда будет выполняться, а переход <code>jnz %condition, @result, @initB</code> всегда будет переходить на ветвь <code>@result</code>. Но если сравнение, например, в <code>@initA</code> в переменную <code>%a</code> положить не 1, а 3, то условие будет всегда ложным, тогда переход будет всегда выполняться на ветвь <code>@initB</code>, и результатом выполнения программы будет <code>%c = 3 (т.к. a = 3) + 2 (т.к. в b будет лежать 2) = 5</code><br />
<br />
== Массивы ==<br />
<br />
Предположим, у нас имеется массив байтов <code>array</code> неопределенного размера и некоторое целое беззнаковое число N. Для работы с N-ным элементом массива придется завести дополнительную переменную (дабы не утратить указатель на первые N элементов), в которой будет размещена сумма адреса первого элемента массива и сдвига на N байт.<br />
%arrayN = l add %array, %N<br />
Теперь с помощью <code>arrayN</code> и инструкций <code>load</code> и <code>store</code> можно получить и записать (соответственно) в N-ный элемент массива <code>array</code>.</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=QBE&diff=52QBE2018-03-18T14:52:22Z<p>Admin: </p>
<hr />
<div><strong>QBE IL (QBE intermediate language)</strong> - промежуточный язык, является языком более высокого уровня, чем язык ассемблера. Он сглаживает большинство проблем базового оборудования и позволяет использовать бесконечное количество временных конструкций. Этот более высокий уровень абстракции позволяет сторонним программистам сосредоточиться на проблемах разработки языка.<br />
<pre>The intermediate language (IL) is a higher-level language than the machine's assembly language. It smoothes most of the irregularities of the underlying hardware and allows an infinite number of temporaries to be used. This higher abstraction level allows frontend programmers to focus on language design issues.</pre><br />
<br />
<div style="float:right;">__TOC__</div><br />
<br />
== Входные файлы ==<br />
<br />
Промежуточный язык предоставляется QBE в виде текста. Как правило, один файл создается для каждой программы с входного языка интерфейса. IL-файл представляет собой последовательность определений для данных, функций и типов. После обработки QBE полученный файл может быть собран и связан с использованием стандартного инструментального ПО (например, [https://ru.wikipedia.org/wiki/GNU_Binutils GNU_binutils]).<br />
<pre>The intermediate language is provided to QBE as text. Usually, one file is generated per each compilation unit from the frontend input language. An IL file is a sequence of Definitions for data, functions, and types. Once processed by QBE, the resulting file can be assembled and linked using a standard toolchain (e.g., GNU binutils).</pre><br />
<br />
Ниже приведено полное содержимое IL-файла "Hello World", в котором определена функция, выводящая на экран "hello world". Поскольку строка не является объектом штатным объектом (только указатель) языка, она определяется вне тела функции. Комментарии начинаются с символа <strong>#</strong> и заканчиваются концом строки.<br />
<pre>Here is a complete "Hello World" IL file which defines a function that prints to the screen. Since the string is not a first class object (only the pointer is) it is defined outside the function's body. Comments start with a # character and finish with the end of the line.</pre><br />
<br />
# Объявление константной строки "hello world"<br />
data $str = { b "hello world", b 0 }<br />
<br />
function w $main() {<br />
@start<br />
# Вызов функции puts с аргументом $str.<br />
%r =w call $puts(l $str)<br />
ret 0<br />
}<br />
<br />
Если вы прочитали ссылку про язык [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM], вы можете понять вышеприведенный код. В сравнении, QBE предоставляет гораздо более простое использование типов и синтаксиса.<br />
<pre>If you have read the LLVM language reference, you might recognize the example above. In comparison, QBE makes a much lighter use of types and the syntax is terser.</pre><br />
<br />
== Запись БНФ == <br />
<br />
Синтаксис языка, который Вы сможете найти в разделах данной Wiki (и в оригинальной документации), описан с использованием [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ]. Различные используемые конструкции [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] перечислены ниже.<br />
<br />
Ключевые слова заключены в кавычки;<br />
... | ... выражает дизъюнкции;<br />
[ ... ] обозначает некоторый синтаксис как необязательный;<br />
( ... ), обозначает разделенный запятыми список прилагаемого синтаксиса;<br />
...* и ...+ используются для произвольных обозначений и для повторений соответственно.<br />
<br />
== Символы ==<br />
<br />
Промежуточный язык изобилует разными символами, все пользовательские имена выделяются символьным префиксом. Это делается для предотвращения конфликтов ключевых слов, а также для быстрого определения области видимости и характера идентификаторов.<br />
<pre>The intermediate language makes heavy use of sigils, all user-defined names are prefixed with a sigil. This is to avoid keyword conflicts, and also to quickly spot the scope and nature of identifiers.</pre><br />
<br />
<code>:</code> используется для определенных пользователем [[Составные типы данных | составных типов данных]]<br />
<code>$</code> используется для глобальных переменных (представленных в виде указателя)<br />
<code>%</code> используется для переменных внутри [[Функции | функций]]<br />
<code>@</code> используется для обозначения меток [[Блоки | блоков]]<br />
<br />
В этом синтаксисе [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] мы используем <code>?IDENT</code> для обозначения идентификатора, начинающегося с символа <code>?</code>.<br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Basic-Concepts c9x.me]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=QBE&diff=51QBE2018-03-18T12:09:06Z<p>Admin: </p>
<hr />
<div><div style="float:right;">__TOC__</div><br />
<br />
<table><tr><td><br />
<br />
<strong>QBE IL (QBE intermediate language)</strong> - промежуточный язык, является языком более высокого уровня, чем язык ассемблера. Он сглаживает большинство проблем базового оборудования и позволяет использовать бесконечное количество временных конструкций. Этот более высокий уровень абстракции позволяет сторонним программистам сосредоточиться на проблемах разработки языка.<br />
<pre>The intermediate language (IL) is a higher-level language than the machine's assembly language. It smoothes most of the irregularities of the underlying hardware and allows an infinite number of temporaries to be used. This higher abstraction level allows frontend programmers to focus on language design issues.</pre><br />
<br />
== Входные файлы ==<br />
<br />
Промежуточный язык предоставляется QBE в виде текста. Как правило, один файл создается для каждой программы с входного языка интерфейса. IL-файл представляет собой последовательность определений для данных, функций и типов. После обработки QBE полученный файл может быть собран и связан с использованием стандартного инструментального ПО (например, [https://ru.wikipedia.org/wiki/GNU_Binutils GNU_binutils]).<br />
<pre>The intermediate language is provided to QBE as text. Usually, one file is generated per each compilation unit from the frontend input language. An IL file is a sequence of Definitions for data, functions, and types. Once processed by QBE, the resulting file can be assembled and linked using a standard toolchain (e.g., GNU binutils).</pre><br />
<br />
Ниже приведено полное содержимое IL-файла "Hello World", в котором определена функция, выводящая на экран "hello world". Поскольку строка не является объектом штатным объектом (только указатель) языка, она определяется вне тела функции. Комментарии начинаются с символа <strong>#</strong> и заканчиваются концом строки.<br />
<pre>Here is a complete "Hello World" IL file which defines a function that prints to the screen. Since the string is not a first class object (only the pointer is) it is defined outside the function's body. Comments start with a # character and finish with the end of the line.</pre><br />
<br />
# Объявление константной строки "hello world"<br />
data $str = { b "hello world", b 0 }<br />
<br />
function w $main() {<br />
@start<br />
# Вызов функции puts с аргументом $str.<br />
%r =w call $puts(l $str)<br />
ret 0<br />
}<br />
<br />
Если вы прочитали ссылку про язык [https://ru.wikipedia.org/wiki/Low_Level_Virtual_Machine LLVM], вы можете понять вышеприведенный код. В сравнении, QBE предоставляет гораздо более простое использование типов и синтаксиса.<br />
<pre>If you have read the LLVM language reference, you might recognize the example above. In comparison, QBE makes a much lighter use of types and the syntax is terser.</pre><br />
<br />
== Запись БНФ == <br />
<br />
Синтаксис языка, который Вы сможете найти в разделах данной Wiki (и в оригинальной документации), описан с использованием [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ]. Различные используемые конструкции [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] перечислены ниже.<br />
<br />
Ключевые слова заключены в кавычки;<br />
... | ... выражает дизъюнкции;<br />
[ ... ] обозначает некоторый синтаксис как необязательный;<br />
( ... ), обозначает разделенный запятыми список прилагаемого синтаксиса;<br />
...* и ...+ используются для произвольных обозначений и для повторений соответственно.<br />
<br />
== Символы ==<br />
<br />
Промежуточный язык изобилует разными символами, все пользовательские имена выделяются символьным префиксом. Это делается для предотвращения конфликтов ключевых слов, а также для быстрого определения области видимости и характера идентификаторов.<br />
<pre>The intermediate language makes heavy use of sigils, all user-defined names are prefixed with a sigil. This is to avoid keyword conflicts, and also to quickly spot the scope and nature of identifiers.</pre><br />
<br />
<code>:</code> используется для определенных пользователем [[Составные типы данных | составных типов данных]]<br />
<code>$</code> используется для глобальных переменных (представленных в виде указателя)<br />
<code>%</code> используется для переменных внутри [[Функции | функций]]<br />
<code>@</code> используется для обозначения меток [[Блоки | блоков]]<br />
<br />
В этом синтаксисе [https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура БНФ] мы используем <code>?IDENT</code> для обозначения идентификатора, начинающегося с символа <code>?</code>.<br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Basic-Concepts c9x.me]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=Data&diff=50Data2018-03-17T15:31:44Z<p>Admin: Новая страница: « DATADEF := ['export'] 'data' $IDENT '=' '{' ( EXTTY DATAITEM+ | 'z' NUMBER ), '}' DATAITEM := $IDENT ['+' NUMBER] # С…»</p>
<hr />
<div> DATADEF :=<br />
['export'] 'data' $IDENT '='<br />
'{'<br />
( EXTTY DATAITEM+<br />
| 'z' NUMBER ),<br />
'}'<br />
DATAITEM :=<br />
$IDENT ['+' NUMBER] # Символ и смещение (offset)<br />
| '"' ... '"' # Строка<br />
| CONST # Константа<br />
<br />
[[Объявления | Объявление]] Data выражает объекты, которые будут присутствовать в скомпилированном файле. Они могут быть локальными для файла или экспортироваться с глобальной видимостью для всей программы (если она состоит из нескольких файлов).<br />
<pre>Data definitions express objects that will be emitted in the compiled file. They can be local to the file or exported with global visibility to the whole program.</pre><br />
<br />
Они определяют глобальный идентификатор (начиная с символа <code>$</code>), который будет содержать указатель на объект, указанный в объявлении.<br />
<pre>They define a global identifier (starting with the sigil $), that will contain a pointer to the object specified by the definition.</pre><br />
<br />
Объекты описываются последовательностью полей, начинающихся с буквы типа. Эта буква может быть либо расширенным типом, либо буквой <code>z</code>. Если используемая буква является расширенным типом, то следующий элемент Data указывает биты, которые должны храниться в поле. Когда несколько элементов Data следуют букве, они инициализируют несколько полей одного размера.<br />
<pre>Objects are described by a sequence of fields that start with a type letter. This letter can either be an extended type, or the z letter. If the letter used is an extended type, the data item following specifies the bits to be stored in the field. When several data items follow a letter, they initialize multiple fields of the same size.</pre><br />
<br />
Члены структуры будут упакованы. Это означает, что содержимое должно быть выбрано интерфейсом, когда это необходимо. Выравнивание всех объектов данных может быть задано вручную, а при отсутствии выравнивания используется максимальное выравнивание с платформы.<br />
<pre>The members of a struct will be packed. This means that padding has to be emitted by the frontend when necessary. Alignment of the whole data objects can be manually specified, and when no alignment is provided, the maximum alignment from the platform is used.</pre><br />
<br />
Когда используется буква <code>z</code>, следующее число указывает размер поля; содержимое поля инициализируется нулем. Его можно использовать для добавления дополнений между полями или больших массивов, инициализированных нулями.<br />
<pre>When the z letter is used the number following indicates the size of the field; the contents of the field are zero initialized. It can be used to add padding between fields or zero-initialize big arrays.</pre><br />
<br />
Ниже приводится пример объявления Data.<br />
<pre>Here are various examples of data definitions.</pre><br />
<br />
# Три 32-битных значения 1, 2 и 3<br />
# за которыми следует 0 байт.<br />
data $a = { w 1 2 3, b 0 }<br />
# Массив из 1000 байт, заполненных нулем.<br />
data $b = { z 1000 }<br />
# Объект, содержащий два 64-битных<br />
# поля. У первого все биты заполнены.<br />
# А второе содержит указатель на объект.<br />
data $c = { l -1, l $c }<br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Data c9x.me]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8&diff=49Функции2018-03-17T15:20:15Z<p>Admin: Новая страница: « FUNCDEF := ['export'] 'function' [ABITY] $IDENT '(' (PARAM), ')' '{' BLOCK+ '}' PARAM := ABITY %IDENT # Regular parameter | 'env…»</p>
<hr />
<div> FUNCDEF :=<br />
['export'] 'function' [ABITY] $IDENT '(' (PARAM), ')'<br />
'{'<br />
BLOCK+<br />
'}'<br />
PARAM :=<br />
ABITY %IDENT # Regular parameter<br />
| 'env' %IDENT # Environment parameter (first)<br />
| '...' # Variadic marker (last)<br />
ABITY := BASETY | :IDENT<br />
<br />
[[Объявления]] функций содержат фактический код для размещения в скомпилированном файле. Они определяются глобальным символом, содержащим указатель на код функции. Этот указатель может использоваться в инструкциях вызова или храниться в памяти.<br />
<pre>Function definitions contain the actual code to emit in the compiled file. They define a global symbol that contains a pointer to the function code. This pointer can be used in call instructions or stored in memory.</pre><br />
<br />
Тип, записанный прямо перед именем функции, является возвращаемым типом функции. Все возвращаемые значения этой функции должны иметь этот же возвращаемый тип. Если возвращаемый тип отсутствует, функция не может вернуть какое-либо значение.<br />
<pre>The type given right before the function name is the return type of the function. All return values of this function must have this return type. If the return type is missing, the function cannot return any value.</pre><br />
<br />
Список параметров представляет собой список временных переменных, разделенных запятыми, с указанием их типов. Типы используются для правильной реализации совместимости Cи. Когда тип аргумента является [[Составные типы данных | составным]], указатель на него передается при вызове функции. В приведенном ниже примере мы должны использовать команду <code>load</code> для получения значения первого (и единственного) элемента структуры.<br />
<pre>The parameter list is a comma separated list of temporary names prefixed by types. The types are used to correctly implement C compatibility. When an argument has an aggregate type, a pointer to the aggregate is passed by the caller. In the example below, we have to use a load instruction to get the value of the first (and only) member of the struct.</pre><br />
<br />
type :one = { w }<br />
function w $getone(:one %p) {<br />
@start<br />
%val =w loadw %p<br />
ret %val<br />
}<br />
<br />
Если список параметров заканчивается на <code>...</code>, функция является [https://ru.wikipedia.org/wiki/Вариативная_функция вариативной]: она может принимать переменное количество аргументов. Для доступа к дополнительным аргументам, подаваемым при вызове функции, используйте инструкции <code>largeart</code> и <code>vaarg</code>, описанные в разделе [[Вариативность]].<br />
<pre>If the parameter list ends with ..., the function is a variadic function: it can accept a variable number of arguments. To access the extra arguments provided by the caller, use the vastart and vaarg instructions described in the Variadic section.</pre><br />
<br />
Вообще, список параметров может начинаться с параметра среды <code>env %e</code>. Этот специальный параметр является 64-битной целочисленной переменной (то есть типа l - long). Если функция не использует свой параметр среды, вызовы функции могут ее опустить. Этот параметр невидим для вызова в Cи: например, функция...<br />
<pre>Optionally, the parameter list can start with an environment parameter env %e. This special parameter is a 64-bit integer temporary (i.e., of type l). If the function does not use its environment parameter, callers can safely omit it. This parameter is invisible to a C caller: for example, the function</pre><br />
<br />
export function w $add(env %e, w %a, w %b) {<br />
@start<br />
%c =w add %a, %b<br />
ret %c<br />
}<br />
<br />
... должна быть предоставлена на Cи как <code>int add (int, int)</code>. Предполагаемое использование этой функции - передать указатель окружения, сохраняя при этом совместимость с Cи. Раздел «[[Инструкция Call]]» объясняет, как передать параметр среды.<br />
<pre>must be given the C prototype int add(int, int). The intended use of this feature is to pass the environment pointer of closures while retaining a very good compatibility with C. The Call section explains how to pass an environment parameter.</pre><br />
<br />
Поскольку глобальные символы определены взаимно рекурсивно, нет необходимости в объявлениях функций: функция может быть использована до своего объявления. Аналогично, функции из других модулей могут использоваться без предварительного объявления. Вся информация о типе указана в статье об [[Инструкция Call | инструкциях вызова]].<br />
<pre>Since global symbols are defined mutually recursive, there is no need for function declarations: a function can be referenced before its definition. Similarly, functions from other modules can be used without previous declaration. All the type information is provided in the call instructions.</pre><br />
<br />
Синтаксис и семантика для тела функций описаны в разделах «[[Блоки]]» и «[[Переходы]]».<br />
<pre>The syntax and semantics for the body of functions are described in the Control section.</pre><br />
<br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Functions c9x.me]</div>Adminhttps://compilers.ispras.ru/wiki/index.php?title=%D0%98%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%86%D0%B8%D0%B8_QBE&diff=48Инструкции QBE2018-03-17T13:06:49Z<p>Admin: Новая страница: «<div style="-moz-column-count:2; column-count:2; -webkit-column-count:2"> <ul><div> <li>Арифметические и битовые операции:</li>…»</p>
<hr />
<div><div style="-moz-column-count:2; column-count:2; -webkit-column-count:2"><br />
<ul><div><br />
<li>[[Арифметические и битовые операции]]:</li><br />
<br />
<code>add</code>,<br />
<code>and</code>,<br />
<code>div</code>,<br />
<code>mul</code>,<br />
<code>or</code>,<br />
<code>rem</code>,<br />
<code>sar</code>,<br />
<code>shl</code>,<br />
<code>shr</code>,<br />
<code>sub</code>,<br />
<code>udiv</code>,<br />
<code>urem</code>,<br />
<code>xor</code>.<br />
<br><br></div><div><br />
<li>[[Память]]:</li><br />
<br />
<code>alloc16</code>,<br />
<code>alloc4</code>,<br />
<code>alloc8</code>,<br />
loadd</code>,<br />
<code>loadl</code>,<br />
<code>loads</code>,<br />
<code>loadsb</code>,<br />
<code>loadsh</code>,<br />
<code>loadsw</code>,<br />
<code>loadub</code>,<br />
<code>loaduh</code>,<br />
<code>loaduw</code>,<br />
<code>loadw</code>,<br />
<code>storeb</code>,<br />
<code>stored</code>,<br />
<code>storeh</code>,<br />
<code>storel</code>,<br />
<code>stores</code>,<br />
<code>storew</code>.<br />
<br><br></div><div><br />
<li>[[Сравнения]]:</li><br />
<br />
<code>ceqd</code>,<br />
<code>ceql</code>,<br />
<code>ceqs</code>,<br />
<code>ceqw</code>,<br />
<code>cged</code>,<br />
<code>cges</code>,<br />
<code>cgtd</code>,<br />
<code>cgts</code>,<br />
<code>cled</code>,<br />
<code>cles</code>,<br />
<code>cltd</code>,<br />
<code>clts</code>,<br />
<code>cned</code>,<br />
<code>cnel</code>,<br />
<code>cnes</code>,<br />
<code>cnew</code>,<br />
<code>cod</code>,<br />
<code>cos</code>,<br />
<code>csgel</code>,<br />
<code>csgew</code>,<br />
<code>csgtl</code>,<br />
<code>csgtw</code>,<br />
<code>cslel</code>,<br />
<code>cslew</code>,<br />
<code>csltl</code>,<br />
<code>csltw</code>,<br />
<code>cugel</code>,<br />
<code>cugew</code>,<br />
<code>cugtl</code>,<br />
<code>cugtw</code>,<br />
<code>culel</code>,<br />
<code>culew</code>,<br />
<code>cultl</code>,<br />
<code>cultw</code>,<br />
<code>cuod</code>,<br />
<code>cuos</code>.<br />
<br><br></div><div><br />
<li>[[Преобразования]]:</li><br />
<br />
<code>dtosi</code>,<br />
<code>exts</code>,<br />
<code>extsb</code>,<br />
<code>extsh</code>,<br />
<code>extsw</code>,<br />
<code>extub</code>,<br />
<code>extuh</code>,<br />
<code>extuw</code>,<br />
<code>sltof</code>,<br />
<code>stosi</code>,<br />
<code>swtof</code>,<br />
<code>truncd</code>.<br />
<br><br></div><div><br />
<li>[[Инструкции Cast и Copy]]:</li><br />
<br />
<code>cast</code>,<br />
<code>copy</code>.<br />
<br><br></div><div><br />
<li>[[Инструкция Call]]:</li><br />
<br />
<code>call</code>.<br />
<br><br></div><div><br />
<li>[[Вариативность]]:</li><br />
<br />
<code>vastart</code>,<br />
<code>vaarg</code>.<br />
<br><br></div><div><br />
<li>[[Инструкция Phi]]:</li><br />
<br />
<code>phi</code>.<br />
<br><br></div><div><br />
<li>[[Переходы]]:</li><br />
<br />
<code>jmp</code>,<br />
<code>jnz</code>,<br />
<code>ret</code>.<br />
</div><br />
</ul><br />
</div><br />
<br />
----<br />
Источник: [http://c9x.me/compile/doc/il.html#Instructions-Index c9x.me]</div>Admin