Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 02 июн 2025, 16:20

Часовой пояс: UTC + 2 часа




Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 8  След.
Автор Сообщение
СообщениеДобавлено: 13 май 2013, 19:02 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Ввел оптимизацию реализации некоторых частных случаев цикла FOR id := A TO B BY Step DO:
1) (Step=1 , B= -1 ) и (Step = -1 , B= 1)
Код: "OBERON"
  1. (*1.Случаи (Step=1 , B= -1 ) и (Step = -1 , B= 1) должны рассматриваться как*)
  2. id := A;
  3. IF A <= -1 THEN (* IF A>= 1 THEN , для Step = -1*)
  4. REPEAT
  5. тело цикла
  6. INC(id, Step);
  7. UNTIL id=0;
  8. END


2) (Step=1 или -1, B= 0 )
Код: "OBERON"
  1. (*2.Случаи (Step=1 или -1 , B= 0 ) должны рассматриваться как*)
  2. id := A;
  3. IF A <= 0 THEN (* IF A>= 0 THEN , для Step = -1*)
  4. DEC(id,Step);
  5. REPEAT
  6. INC(id, Step);
  7. тело цикла
  8. UNTIL id=0;
  9. END


Получилось довольно запутано:
Код: "OBERON"
  1.  
  2. ELSIF sym = for THEN (* построение синтаксического дерева для FOR *)
  3. OPS.Get(sym); (* взять символ после FOR *)
  4. IF sym = ident THEN qualident(id); (* если это идентификатор, уточнить его *)
  5. IF ~(id^.typ^.form IN intSet) THEN err(68) END ;(* он должен быть целого типа*)
  6. CheckSym(becomes); Expression(y); pos := OPM.errpos; (* потом д б «:= выражение (А)» *)
  7. x := OPB.NewLeaf(id); OPB.Assign(x, y); SetPos(x);(* вставим в дерево «id := А» *)
  8. OPB.Link(stat, last, x); (* не очень понятно, похоже как-то связано с присваиванием*)
  9. CheckSym(to); Expression(y); pos := OPM.errpos; (* далее д б ТО выражение (В) *)
  10. IF sym = by THEN (* если далее задан шаг BY Step,*)
  11. OPS.Get(sym); ConstExpression(z) (* то читаем его как константное выражение*)
  12. ELSE
  13. z := OPB.NewIntConst(1) (*иначе берем константу 1*)
  14. END ;
  15. (* если В задается константой *)
  16. IF (y^.class = Nconst) THEN
  17. IF (y^.typ^.form < SInt) OR (y^.typ^.form > x^.left^.typ^.form) THEN
  18. err(113); t := NIL; (* то это д б константа совместимого типа *)
  19. ELSIF (z^.conval^.intval=1)&(y^.conval^.intval=-1) OR (* частные случаи, когда *)
  20. (z^.conval^.intval=-1)&(y^.conval^.intval=1) OR (*переменная t не нужна*)
  21. ( ABS(z^.conval^.intval) = 1 ) & ( y^.conval^.intval=0) THEN
  22. t:=NIL; (* переменная t не нужна*)
  23. ELSE
  24. name := "@@"; OPT.Insert(name, t); t^.name := "@for"; (* нужна переменная t*)
  25. END
  26. ELSE (* B - не константа *)
  27. name := "@@"; OPT.Insert(name, t); t^.name := "@for"; (* нужна переменная t*)
  28. END;
  29. IF t # NIL THEN
  30. t^.mode := Var; t^.typ := x^.left^.typ; (* в таблице имен создаем*)
  31. obj := OPT.topScope^.scope; (*вспомогательную *)
  32. IF obj = NIL THEN OPT.topScope^.scope := t (* переменную t для счетчика повторений*)
  33. ELSE
  34. WHILE obj^.link # NIL DO obj := obj^.link END ;
  35. obj^.link := t
  36. END ;
  37. END;
  38. IF t # NIL THEN
  39. x:= OPB.NewLeaf(t); OPB.Assign(x, y); SetPos(x); (* t := B*)
  40. OPB.Link(stat, last, x);
  41. pos := OPM.errpos; (* теперь ошибка будет указывать на шаг*)
  42. x := OPB.NewLeaf(id);y:=OPB.NewLeaf(t);
  43. (* z = "Step", x = "id", y = "t" *)
  44. IF z^.conval^.intval > 0 THEN (* подготовим выражение "кол-во повторений" *)
  45. OPB.Op(minus, y,x); (* B-x *)
  46. OPB.Op(div, y, OPB.NewIntConst( z^.conval^.intval)); (* (B-x) div Step *)
  47. OPB.Op(plus, y, OPB.NewIntConst(1)); (* (B-x) div Step +1 *)
  48. x := y;
  49. ELSIF z^.conval^.intval < 0 THEN (* в зависимости от знака Step*)
  50. OPB.Op(minus, x, y); (* x-B *)
  51. OPB.Op(div, x, OPB.NewIntConst( -z^.conval^.intval)); (* (x-B) div Step *)
  52. OPB.Op(plus, x, OPB.NewIntConst(1)); (* (x-B) div Step +1 *)
  53. ELSE err(63); OPB.Op(minus, x, y)
  54. END ;
  55. (* x = " (B-x) div Step +1" или "(x-В) div Step +1 " *)
  56. y := OPB.NewLeaf(t);OPB.Assign(y, x); SetPos(y); (* y = "t := (B-x) div Step +1 " *)
  57. ELSE (* без переменной для повторения *)
  58. IF y^.conval^.intval = 0 THEN (* нужно нейтрализовать первый инкремент*)
  59. y := OPB.NewLeaf(id); OPB.StPar1(y, z, decfn); SetPos(y); (* x= "DEC(id,Step)"*)
  60. ELSE
  61. y := OPB.NewLeaf(id); (* y = "id" - фиктивный оператор, т.к. нейтрализация не нужна *)
  62. END
  63. END;
  64. x := OPB.NewLeaf(id); OPB.StPar1(x, z, incfn); SetPos(x); (* x= "INC(id,Step)"*)
  65. y^.link := x; (* t := (B-x) div Step +1; INC(id,Step) *)
  66. IF t # NIL THEN (* добавить DEC(t) *)
  67. x := OPB.NewLeaf(t); OPB.StPar1(x, OPB.NewIntConst(1), decfn); SetPos(x);
  68. y^.link^.link := x; (* t := (B-x) div Step +1; INC(id,Step); DEC(t) *)
  69. END;
  70. CheckSym(do); StatSeq(s); (* дальше д б DO и тело цикла s *)
  71. IF s = NIL THEN
  72. s := y^.link; (* если тело цикла — пусто, то там д б только INC(id,Step);DEC(t) *)
  73. ELSIF (t # NIL) OR (y^.class = Nvar) THEN
  74. x := s; (* иначе ищем конец тела цикла *)
  75. WHILE x^.link # NIL DO x := x^.link END ;
  76. x^.link := y^.link; (* добавляем в конец тела цикла INC(n,Step); [ DEC(t) ]*)
  77. ELSE
  78. y^.link^.link := s; s:=y^.link; (* добавляем в начало тела цикла INC(n,Step); *)
  79. END;
  80. CheckSym(end); (* в конце д б END *)
  81. IF t # NIL THEN
  82. x := OPB.NewLeaf(t); OPB.Op(eql, x, OPB.NewIntConst(0)); (* условие "t = 0" *)
  83. ELSE
  84. x := OPB.NewLeaf(id); OPB.Op(eql, x, OPB.NewIntConst(0)); (* условие "id = 0" *)
  85. END;
  86. OPB.Construct(Nrepeat, s,x);SetPos(s); (* REPEAT ...UNTIL t=0;*)
  87. y^.link := s; (* t := (B-x) div Step +1; REPEAT ... UNTIL t=0; *)
  88. IF y^.class = Nvar THEN s:=y^.link ELSE s:=y END; (* Отбросим фиктивный оператор *)
  89. x := OPB.NewLeaf(id);
  90.  
  91. IF t # NIL THEN y := OPB.NewLeaf(t) ELSE y:= OPB.NewIntConst(- z^.conval^.intval) END;
  92. (* y = <B> = "t" или "-Step" (для условия IF) *)
  93. IF z^.conval^.intval > 0 THEN OPB.Op(leq, x, y) (* условие id <= B *)
  94. ELSIF z^.conval^.intval < 0 THEN OPB.Op(geq, x, y) (* или id >= B*)
  95. ELSE err(63); OPB.Op(geq, x, y)
  96. END ;
  97.  
  98. OPB.Construct(Nif, x, s); SetPos(x); lastif := x; (* строим IF id<=B THEN ...*)
  99. OPB.Construct(Nifelse, x, NIL); (* ветви ELSE нет*)
  100. OPB.OptIf(x); pos := OPM.errpos
  101. ELSE err(ident)
  102. END

Боюсь, еще немного и получим такое "спагетти", что проще будет начать с нуля, чем что-то там исправить. Чтобы этого избежать следует как-то сгруппировать случаи, для которых возможна оптимизация; продумать систему флажков, в которых зафиксируем возможность той или иной оптимизации; продумать связь между вариантами генерируемого С-кода и этими флажками. Сейчас в качестве флажков взял уже используемые Ofront переменные:
    t=NIL - значит вспомогательную переменную t не создаем;
    перед REPEAT UNTIL поставили фиктивный оператор - значит нейтрализация INC(n,Step) не нужна, т.е. это случай (Step=1 или -1 , B=0 ).

Возможен, конечно, еще случай 3) (Step=B = 1 или Step=B = -1). В этом случае требуется заменить условие после UNTIL
Код: "OBERON"
  1. (*3. Случаи (Step=B= 1 ) или (Step = B= -1) должны рассматриваться как*)
  2. id := A;
  3. IF A <= 1 THEN (* IF A>= -1 THEN , для Step = B = -1*)
  4. DEC(id,Step);
  5. REPEAT
  6. INC(id, Step);
  7. тело цикла
  8. UNTIL id>0; (* или UNTIL id <0 для Step = B= -1*)
  9. END
Но правильно ли будет работать id>0 для знаковых и беззнаковых чисел? Не повлияет ли на это сравнение приведение к типу int или переполнение в инкременте? Как-то равенству я больше верю :)

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 13 май 2013, 19:16 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
OPM.errpos — это позиция последней найденной ошибки в исходном тексте модуля. Описывается одним числом (когда я модифицировал OPCL для вывода строки/колонки возникшей ошибки — пришлось ввести вместо одного числа, обозначающего позицию, запись со строкой и колонкой. А может были и ещё доп. поля. Деталей уже не помню).
Спасибо, вроде бы разобрался. Я не мог понять почему иногда делают pos := OPM.errpos, а иногда нет. Как я сейчас думаю, хотя на 100% не уверен: OPM.errpos - это позиция ВОЗМОЖНОЙ ошибки в тексте (место до которого дочитали), а pos - место в тексте с которым процедура SetPos(x) свяжет узел дерева х. Иногда нужно, чтобы pos от errpos отставало: т.е. прочитали из Оберон-программы следующую конструкцию, а строим узел еще для предыдущей (и этот узел надо привязать к предыдущей позиции, что SetPos(x) и делает). А вот когда узлы для всех старых позиций построили, тогда передвигаем pos := OPM.errpos на новую конструкцию (и теперь SetPos(x) свяжет узел х уже с новым местом текста).

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 13 май 2013, 21:40 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Как я сейчас думаю, хотя на 100% не уверен: OPM.errpos - это позиция ВОЗМОЖНОЙ ошибки в тексте (место до которого дочитали), а pos - место в тексте с которым процедура SetPos(x) свяжет узел дерева х.
Да, это запросто может быть.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 14 май 2013, 17:44 
Не в сети
Администратор
Аватара пользователя

Сообщения: 189
Saferoll писал(а):
Спасибо, вроде бы разобрался. Я не мог понять почему иногда делают pos := OPM.errpos, а иногда нет.


Компилятор при первичной проверке отмечает возможные ошибки, которые в будущем надо будет проверить. Например:

Код: "OBERON"
  1. MODULE Forms;
  2.  
  3. IMPORT
  4. SYSTEM, W:=Windows, M:=Messages, C:=Controls, G:=Graphics;
  5.  
  6. VAR
  7. Application*: TApplication;
  8.  
  9. (*............. какой то код ....................*)
  10.  
  11. TYPE
  12. TApplication = POINTER TO RECORD
  13.  
  14. (*...............................................*)


На этапе первого прохода Application*: TApplication; ещё не известна и не определена,
позже мы её описываем как некий тип или запись или переменную ...
Поэтому отметочку на позиции в тексте сделать надо, причём с учетом синтаксического дерева, что бы отмотать назад кусты дерева, вот
тут в принципе и расхождения могут быть довольно значительные с реальной позицией ошибки!!!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 16 май 2013, 20:34 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
При реализации цикла FOR через вычисление количества итераций решил сначала проанализировать выражения В и Step, зафиксировать какой из случаев цикла (1 общий и 3 частных) имеет место, а потом последовательно строить, выбирая тот или иной вариант для каждого узла создаваемого дерева. Фиксация производится в переменных:
    t: для общего случая t - это вспомогательная переменная, содержащая количество итераций (тогда t # id). В частных случаях, когда вспомогательной переменной нет, выполняется присваивание t:= id, что позволяет автоматически строить нужный узел дерева. По условию t # id можно определить, что имеет место общий случай.
    obj: позволяет уточнить какой из 3 частных случаев имеет место:1) obj=NIL (если B = 0), 2)obj = id (при B = Step) или 3) B # Step (obj в этом случае не равно ни id, ни NIL). Кроме того, оказалось удобным для общего случая присвоить obj: = t, чтобы выполнялось obj # id.
Привожу соответствующий фрагмент модуля Ofront.OPP:
Код: "OBERON"
  1. ELSIF sym = for THEN (* построение синтаксического дерева для FOR *)
  2. OPS.Get(sym); (* взять символ после FOR *)
  3. IF sym = ident THEN qualident(id); (* если это идентификатор, уточнить его *)
  4. IF ~(id^.typ^.form IN intSet) THEN err(68) END ;(* он должен быть целого типа*)
  5. CheckSym(becomes); Expression(y); pos := OPM.errpos; (* потом д б «:= выражение (А)» *)
  6. x := OPB.NewLeaf(id); OPB.Assign(x, y); SetPos(x);(* вставим в дерево «id := А» *)
  7. OPB.Link(stat, last, x); (* не очень понятно, похоже как-то связано с присваиванием*)
  8. CheckSym(to); Expression(y); pos := OPM.errpos; (* далее д б ТО выражение (В) *)
  9. IF sym = by THEN (* если далее задан шаг BY Step,*)
  10. OPS.Get(sym); ConstExpression(z) (* то читаем его как константное выражение*)
  11. ELSE
  12. z := OPB.NewIntConst(1) (*иначе берем константу 1*)
  13. END ;
  14. IF (y^.class = Nconst) THEN
  15. IF (y^.typ^.form < SInt) OR (y^.typ^.form > x^.left^.typ^.form) THEN
  16. err(113); t := id; obj := NIL; (* то это д б константа совместимого типа *)
  17. ELSIF (ABS(z^.conval^.intval)=1)& (ABS(y^.conval^.intval) <= 1) THEN
  18. (* частные случаи, когда переменная t не нужна*)
  19. t := id; (* вместо t используем id *)
  20. IF y^.conval^.intval = 0 THEN obj := NIL
  21. ELSIF y^.conval^.intval = z^.conval^.intval THEN obj := id
  22. ELSE obj := z.typ.strobj; ASSERT( obj # id);
  23. END
  24. ELSE
  25. name := "@@"; OPT.Insert(name, t); (* нужна переменная t*)
  26. END
  27. ELSE (* B - не константа *)
  28. name := "@@"; OPT.Insert(name, t); (* нужна переменная t*)
  29. END;
  30. IF t # id THEN
  31. t^.name := "@for" ; t^.mode := Var; t^.typ := x^.left^.typ; (* в таблице имен создаем*)
  32. obj := OPT.topScope^.scope; (*вспомогательную *)
  33. IF obj = NIL THEN OPT.topScope^.scope := t (* переменную t для счетчика повторений*)
  34. ELSE
  35. WHILE obj^.link # NIL DO obj := obj^.link END ;
  36. obj^.link := t
  37. END ;
  38. obj:= t; ASSERT( obj # id);
  39. END;
  40. (* Переменные t и obj задают 4 случая цикла *)
  41. IF t # id THEN
  42. x:= OPB.NewLeaf(t); OPB.Assign(x, y); SetPos(x); (* t := B*)
  43. OPB.Link(stat, last, x);
  44. pos := OPM.errpos; (* теперь ошибка будет указывать на шаг*)
  45. x := OPB.NewLeaf(id);y:=OPB.NewLeaf(t);
  46. (* z = "Step", x = "id", y = "t" *)
  47. IF z^.conval^.intval > 0 THEN (* подготовим выражение "кол-во повторений" *)
  48. OPB.Op(minus, y,x); (* B-x *)
  49. OPB.Op(div, y, OPB.NewIntConst( z^.conval^.intval)); (* (B-x) div Step *)
  50. OPB.Op(plus, y, OPB.NewIntConst(1)); (* (B-x) div Step +1 *)
  51. x := y;
  52. ELSIF z^.conval^.intval < 0 THEN (* в зависимости от знака Step*)
  53. OPB.Op(minus, x, y); (* x-B *)
  54. OPB.Op(div, x, OPB.NewIntConst( -z^.conval^.intval)); (* (x-B) div Step *)
  55. OPB.Op(plus, x, OPB.NewIntConst(1)); (* (x-B) div Step +1 *)
  56. ELSE err(63); OPB.Op(minus, x, y)
  57. END ;
  58. (* x = " (B-x) div Step +1" или "(x-В) div Step +1 " *)
  59. y := OPB.NewLeaf(t);OPB.Assign(y, x); SetPos(y); (* y = "t := (B-x) div Step +1 " *)
  60. ELSE (* без переменной t *)
  61. IF (obj = NIL) OR (obj = id) THEN (* нужно нейтрализовать первый инкремент*)
  62. y := OPB.NewLeaf(id); OPB.StPar1(y, z, decfn); SetPos(y); (* x= "DEC(id,Step)"*)
  63. ELSE
  64. y := OPB.NewLeaf(id); (* y = "id" - фиктивный оператор, т.к. нейтрализация не нужна *)
  65. END
  66. END;
  67. pos := OPM.errpos;
  68. IF z^.conval^.intval=0 THEN err(63) END; (* нулевой шаг недопустим*)
  69. x := OPB.NewLeaf(id); OPB.StPar1(x, z, incfn); SetPos(x); (* x= "INC(id,Step)"*)
  70. y^.link := x; (* t := (B-x) div Step +1; INC(id,Step) *)
  71. IF t # id THEN (* добавить DEC(t) *)
  72. x := OPB.NewLeaf(t); OPB.StPar1(x, OPB.NewIntConst(1), decfn); SetPos(x);
  73. y^.link^.link := x; (* t := (B-x) div Step +1; INC(id,Step); DEC(t) *)
  74. END;
  75. CheckSym(do); StatSeq(s); (* дальше д б DO и тело цикла s *)
  76. IF s = NIL THEN
  77. s := y^.link; (* если тело цикла — пусто, то там д б только INC(id,Step); [ DEC(t) ] *)
  78. ELSIF (obj=NIL) OR (obj = id) THEN
  79. y^.link^.link := s; s:=y^.link; (* добавляем в начало тела цикла INC(n,Step); *)
  80. ELSE (* ищем конец тела цикла *)
  81. x := s;
  82. WHILE x^.link # NIL DO x := x^.link END ;
  83. x^.link := y^.link; (* добавляем в конец тела цикла INC(n,Step); [ DEC(t) ]*)
  84. END;
  85. CheckSym(end); (* в конце д б END *)
  86. IF obj # id THEN
  87. x := OPB.NewLeaf(t); OPB.Op(eql, x, OPB.NewIntConst(0)); (* условие "t = 0" "(id = 0)" *)
  88. ELSE
  89. x := OPB.NewLeaf(id);
  90. IF z^.conval^.intval > 0 THEN OPB.Op(gtr, x, OPB.NewIntConst(0)) (* условие id > 0 *)
  91. ELSIF z^.conval^.intval < 0 THEN OPB.Op(lss, x, OPB.NewIntConst(0)) (* или id < 0 *)
  92. END
  93. END;
  94. OPB.Construct(Nrepeat, s,x);SetPos(s); (* REPEAT ...UNTIL t=0; (id >0, id <0)*)
  95. y^.link := s; (* t := (B-x) div Step +1; REPEAT ... UNTIL t=0; *)
  96. IF y^.class = Nvar THEN (* фиктивный оператор *)
  97. s:=y^.link ; (* отбросим фиктивный оператор*)
  98. ELSE
  99. s:=y
  100. END;
  101. x := OPB.NewLeaf(id); (*начинаем строить условие IF*)
  102. IF t # id THEN y := OPB.NewLeaf(t)
  103. ELSIF obj = NIL THEN y := OPB.NewIntConst(0)
  104. ELSIF obj = id THEN y := z
  105. ELSE y:= OPB.NewIntConst( -z^.conval^.intval )
  106. END;
  107. (* y = <B> = "t" или "+-Step" (для условия IF) *)
  108. IF z^.conval^.intval > 0 THEN OPB.Op(leq, x, y) (* условие id <= B *)
  109. ELSE OPB.Op(geq, x, y); (* или id >= B*)
  110. END ;
  111. OPB.Construct(Nif, x, s); SetPos(x); lastif := x; (* строим IF id<=B THEN ...*)
  112. OPB.Construct(Nifelse, x, NIL); (* ветви ELSE нет*)
  113. OPB.OptIf(x); pos := OPM.errpos
  114. ELSE err(ident)
  115. END
При тестировании для всех 4 случаев (даже для 8-ми , если считать отдельно положительный и отрицательный шаг) получил верные результаты. Но не могу ручаться, что не вылезет какая-то проблема из-за безнаковости чисел или из-за кастования в int.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 17 май 2013, 12:16 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Приступаю к тестированию новой реализации FOR!

Выигрыша по размеру кода конечно пока нету, но зато работает вот это:
Код: "OBERON"
  1. FOR byte := 0 TO P.Unsigned(255) DO
  2. B.PRWORD(byte); B.PRCHAR(" ");
  3. END;

P.S. При сравнении знакового и беззнакового short (без приведения к int) SDCC не ругается. Но нам это мало чем пригодится, т.к. short тоже двухбайтовый.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 17 май 2013, 20:04 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Приступаю к тестированию новой реализации FOR!
Выигрыша по размеру кода конечно пока нету, но зато работает вот это...
Выигрыша по сравнению со стандартным обероновским циклом и не может быть, потому что добавление контроля за переполнением требует добавления дополнительных операторов. Зато реализация FOR через вычисление количества итераций должна давать выигрыш в скорости, но, увы, не во всех случаях. Выигрыш достигается за счет более быстрого сравнения (t=0). Но есть и проигрыш: дополнительная переменная - это проигрыш в памяти, в каждом цикле нужен инкремент (декремент) этой переменной, а перед циклом нужно вычислить количество итераций (трудоемкая в общем случае операция, т.к. требует деления). Поэтому если количество итераций мало, шаг не единичный и\или не степень двойки, то весь выигрыш съедается проигрышем.

И вот, кстати, у меня сомнения относительно реализованных частных случаев.
Сомнения вызывает случай
Код: "OBERON"
  1. (*3. Случаи (Step=B= 1 ) или (Step = B= -1) должны рассматриваться как*)
  2. id := A;
  3. IF A <= 1 THEN (* IF A>= -1 THEN , для Step = B = -1*)
  4. DEC(id,Step);
  5. REPEAT
  6. INC(id, Step);
  7. тело цикла
  8. UNTIL id>0; (* или UNTIL id <0 для Step = B= -1*)
  9. END
Я предположил, что можно эффективно сравнить с нулем не только на равенство, но и на строгое неравенство. А так ли это? Можно ли придумать для Z80 команды не менее эффективные чем использование доп.переменной? Заметим, что в данном случае UNTIL id>0 означает UNTIL id=1 ( UNTIL id<0 эквивалентно id=-1). Поэтому последовательность команд LD A,(var_id); DEC A (или INC A); JR NZ, lab_repeat; заменяет указанный UNTIL.
Точно так же можно поступать в случае 2байтовых значений - выполнить DEC HL (или INC HL) перед сравнением на равенство нулю. Для условия id <0 есть другой способ, возможно более эффективный - проверить старший бит старшего байта, если он установлен, то значение отрицательно.

Мы нашли довольно неплохие команды ассемблера, но как поместить их в конечный код? Модифицировать Ofront, чтобы генерировал ассемблерные вставки вместо операторов Си? Можно, но тогда теряется кроссплатформенность. Более гибким мне представляется следующий подход: Ofront транслирует цикл FOR в некие псевдооперации (repeat_for(id)until_for_Z(id)), которые являются макросами Си. Для дальнейшей трансляции подключается библиотека макросов, зависящая от целевой платформы. В этой библиотеке макросы переводятся в последовательность команд ассемблера , либо в простые операторы С, подходящие всем платформам (например repeat_for(id) - > “do{”, until_for_Z(id) - >”}while (id != 0)”).
Понятно, что такой механизм эффективных макроподстановок можно применить не только для реализации цикла FOR.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 17 май 2013, 23:23 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Выигрыша по сравнению со стандартным обероновским циклом и не может быть, потому что добавление контроля за переполнением требует добавления дополнительных операторов.
Выигрыша я жду, главным образом, в циклах, параметры которых будут константами. А сейчас наверное имеет смысл подготовить набор тестов и заняться оптимизацией. Олег, насколько хорошо ложится на Ofront следующая оптимизация?

Твоя модификация Ofront'а генерирует (бинарник 91 байт):
Код: "C"
export void *ASCII__init(void)
{
ASCII_n = 32;
ASCII__for__1 = 127;
if (ASCII_n <= ASCII__for__1) {
ASCII__for__1 = (ASCII__for__1 - ASCII_n) + 1;
do {
Console_WriteCh((CHAR)ASCII_n);
ASCII_n += 1;
ASCII__for__1 -= 1;
} while (!(ASCII__for__1 == 0));
}
}

В идеале хорошо бы, чтобы генерило (бинарник 66 байт):
Код: "C"
export void *ASCII__init(void)
{
ASCII_n = 32;
ASCII__for__1 = 96;
do {
Console_WriteCh((CHAR)ASCII_n);
ASCII_n += 1;
ASCII__for__1 -= 1;
} while (ASCII__for__1 != 0);
}

Немодифицированный Ofront генерирует для данного кода бинарник размером 88 байт. Вот и выигрыш, притом и в размере кода, и в скорости.

А потери на вычисление количества повторов цикла (при неконстантных параметрах цикла) не смущают. Для Z80 деление — это вызов подпрограммы. Размер кода минимальный. Потери скорости — гораздо ниже, чем при добавлении контроля за переполнением внутри цикла. А в случае деления на нечто кратное двум — SDCC оптимизирует деление до сдвига. Так что это очень приемлемо.

Крайне не советую тебе морочиться с асмом и макросами. Подобные оптимизации надо делать на уровне Си-в-асм, продвигая идеи по кодогенерации/оптимизации Филиппу Клаусу Краузе, разработчику кодогенератора Z80 для SDCC. А если не брать во внимание SDCC, то все эти оптимизации умеет делать любой приличный компилятор Си. Впрочем, если удастся сделать оптимизацию, перенеся вычисления и сравнения константных выражений с рантайма в compile-time, как я показал выше, — уже получится очень приличный цикл FOR, которым я буду пользоваться весьма охотно.

Выигрыш от твоей реализации FOR (если реализовать константную оптимизацию) на исходнике “Дурака” может составить больше килобайта, если брать примерно 22 байта выигрыша на каждом цикле FOR, а их там не менее сотни.


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 18 май 2013, 06:12 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Выигрыша я жду, главным образом, в циклах, параметры которых будут константами. А сейчас наверное имеет смысл подготовить набор тестов и заняться оптимизацией. Олег, насколько хорошо ложится на Ofront следующая оптимизация?...
Замена вычисления количества итераций константой и удаление IF с константным условием? Думаю это несложно сделать. Кстати, обнаружил, что SDCC делает это сам.
Цитата:
А потери на вычисление количества повторов цикла (при неконстантных параметрах цикла) не смущают. Для Z80 деление — это вызов подпрограммы. Размер кода минимальный. Потери скорости — гораздо ниже, чем при добавлении контроля за переполнением внутри цикла. А в случае деления на нечто кратное двум — SDCC оптимизирует деление до сдвига. Так что это очень приемлемо.
Замену деления на сдвиг делает сам Ofront, причем еще при построении дерева.
Цитата:
Крайне не советую тебе морочиться с асмом и макросами. Подобные оптимизации надо делать на уровне Си-в-асм, продвигая идеи по кодогенерации/оптимизации Филиппу Клаусу Краузе, разработчику кодогенератора Z80 для SDCC. А если не брать во внимание SDCC, то все эти оптимизации умеет делать любой приличный компилятор Си.
Конечно, хорошо, когда есть глобальные оптимизации на уровне самого компилятора. Но в С-исходнике может не хватать некоторой информации. Например не видно, что этот do while (id=0); является реализацией цикла FOR и поэтому id после завершения цикла можно испортить или использовать в своих целях.
Если мы применим макросы, то такая информация будет. Исходник на Си превратится в прогу на неком "псевдоСи" (или лучше назвать "макроСи"?), операторы которого несут дополнительную информацию и могут быть оптимизированы более качественно. Т.е. появляется дополнительный уровень: Оберон -> макроСи -> Си -> Ассемблер. И "макро" могут транслироваться сразу на уровень Ассемблера, если для них придуманы эффективные ассемблерные команды.А если еще не придумали, то этот "макро" легко превращается обратно в Си.
Впрочем, Олег, ты прав, что оптимизация на более высоком уровне сейчас важнее.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 18 май 2013, 16:39 
Не в сети
Аватара пользователя

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Замена вычисления количества итераций константой и удаление IF с константным условием? Думаю это несложно сделать. Кстати, обнаружил, что SDCC делает это сам.
Та да, меня SDCC тоже часто радует изысканной оптимизацией.
Кстати, я выяснил, что разница 66/91 байт вызвана не этими IF и лишним присваиванием, а разницей в кодогенерации между типами SHORTINT и INTEGER. Но всё-таки наверное будет правильно не загромождать Си-исходник лишними инструкциями, если можно и без них.

Saferoll писал(а):
Замену деления на сдвиг делает сам Ofront, причем еще при построении дерева.
:) И SDCC это тоже делает.

Saferoll писал(а):
Конечно, хорошо, когда есть глобальные оптимизации на уровне самого компилятора. Но в С-исходнике может не хватать некоторой информации. Например не видно, что этот do while (id=0); является реализацией цикла FOR и поэтому id после завершения цикла можно испортить или использовать в своих целях.
Но ведь на самом деле нам Си-исходник нужен только как промежуточное хорошо стандартизированное представление, с которого есть много готовых качественных бэк-эндов для разных процессоров. Анализировать и изучать Си-код, сгенерированный Ofront'ом, мы будем по минимуму. И уж точно анализировать и изучать код (а также автоматически модифицировать) лучше на уровне Оберона. Что бы там кто ни говорил, но я считаю синтаксис и семантику Оберон-языков очень удачными, и не склонен относить ключевые слова в верхнем регистре к рудиментарному неудобству, как считают многие сишники. Напротив, считаю это структурным скелетом кода и большим удобством. Если вижу идеальный язык программирования, то это будет расширенное хорошо продуманным набором средств надмножество Компонентного Паскаля. Кстати, обращаю твоё внимание, что в исходной реализации Ofront тоже не помещает в Си-исходник достаточную информацию, что while является реализацией FOR (это можно понять разве что по имени переменной xxx__for__1).

Так что я бы продвигал хитрые оптимизации для Z80 в сообщество SDCC, пусть каждый делает свою работу. Они — хорошую кодогенерацию для Z80, а мы — хорошее кроссплатформенное усовершенствование Оберона-2 и эффективное средство для разработки самого широкого класса программ.

Saferoll писал(а):
Впрочем, Олег, ты прав, что оптимизация на более высоком уровне сейчас важнее.
Спасибо! А я могу пока заняться тестированием FOR.


Вернуться к началу
 Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 8  След.

Часовой пояс: UTC + 2 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
© VEDAsoft Oberon Club