nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Транслятор QuatCore: первый успех по Hazard'ам

Промучался ещё немного. Что-то я поначалу думал сделать обнаружение Hazard'ов отдельным этапом, и уже почти что написал, как стало ясно - тогда и адресация вся слетает нахрен! Когда мы всё перекодировали в машинный код, нам будет очень сложно все переходы, условные и безусловные, подправить.

Так что на самом деле нужно их ловить "на лету" - только декодировал очередную команду в исходном .asm-файле - и прежде чем сразу её добавить "на выход", нужно проверить, мешает ли она предыдущей, и если да - принять карантинные меры, обеспечить между ними дистанцию, а уже потом добавить эту команду. Вот тогда красота. Ну, не самый красивый код, но всё же весьма компактный:

    if CodeRamIndex > 0 then begin
      prevSrc := SrcByAdr[CodeSeg[CodeRamIndex-1].comand.src];
      prevDest := DestByAdr[CodeSeg[CodeRamIndex-1].comand.dest];
      v := SrcByAdr[com.src];
      if (prevDest.Resources * v.Resources <> []) and not (prevSrc.CreatesBubble) then begin
        //Вот он HAZARD, великий и ужасный
        log(Format('Конфликт (Hazard) между командами %s и %s, процедура %s, строки:',[prevDest.Key, v.Key, curProc]));
        log(DebugCodeLines[DebugCodeLines.Count-1]);
        log(origLine);
        log('Вставляем NOP');
        log('');
        DebugCodeLines.Add('    NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD');
        StoreToCode(CodeRamIndex,NOP);
        inc(CodeRamIndex);
        if LabelIndex > 0 then
          Labels.Objects[LabelIndex] := TObject(CodeRamIndex); //чтобы не прыгать на NOP
      end;
    end;


А разговоров-то было! (раз, два, три, четыре)

Проверим это дело на программе нахождения наиболее удалённой точки из четырёх, ту, которую мы "ручками" отладили, но это было тяжело (раз, два, три, четыре, пять.


Возьмём неотредактированный код, где все HAZARDы ещё присутствуют (не исправлены "вручную"):

.code
;основная программа
main proc
		SP		StackAdr
		SP		[SP]		;тут должен быть HAZARD (чтение по адресу из SP, который ещё не записался)

		CALL		AffineAlgorithm
@@endless:	JMP		@@endless
main endp

;Аффинный алгоритм, он же алгоритм захвата
;содержание регистров произвольное, сохранять его не требуется
;исходные данные - Points2D - координаты 4 точек на фотоприёмной матрице,
;неупорядоченные.
AffineAlgorithm 	proc

	;алгоритм переупорядочивает точки "на месте", в порядке МДД3-МДД1-МБД-МДД2 (т.е против часовой стрелки от МДД3)
	Associate4Points	proc
	
		;состояние регистров неизвестно (за искл. PC и SP)
		FindMDD3	proc
		;перво-наперво, находим МДД3
		;как точка, сумма квадратов расстояний до которой максимальна (т.е самая отдалённая)
		;для каждой точки считаем сумму квадр. расстояний до всех остальных, в т.ч до самой себя (это 0, зато код упрощается)
		;внешний цикл (по строкам) - перем. j
		;внутр. цикл (по столбцам) - перем. i
		;самый-самый внутр. цикл - по индексу перем (X или Y) - перем k
				Y		Points2D
				[SP+1]		0	;максимальная отдалённость, инициализируем нулём
				;рег. Y будет хранить индекс точки с макс. отд. её иниц. не надо-заведомо на одной из итераций запишется
					
				;ijk			-61	;j=3, Inv=1 (пригодится в дальнейшем!)
				;попытаемся пока обойтись без ijk, уж больно он толстый
				j		3
		@@j_loop:	k		1	;также от 0 до 3, чтобы все расстояния просуммировать
				[SP]		0	;здесь будет храниться текущий максимум
		@@k_loop:	i		3	;от 0 до 1, т.е значения X и Y
		;а теперь непосредственно прибавляем к акк. ([X+2i+k]-[X+2j+k])^2
		@@i_loop:	Acc		[Y+2i+k]	;тут должен быть HAZARD (обращение по [Y+2i+k] происходит по предыдущему значению i)
				SUB		[Y+2j+k]	;вычитаем второе
				SQRD2		Acc			;возводим в квадрат
				ADD		[SP]		;прибавляем к пред. значению
				[SP]		Acc
				iLOOP		@@i_loop		;теперь то же самое для второй координаты
				kLOOP		@@k_loop
		;хорошо, нашли сумму расстояний от точки j до всех остальных
		;она лежит в Acc и в [SP]
		;нужно сравнить с самым большим, и если больше - заменить
		;самое большое значение мы храним в [SP+1],
		;а его индекс - в [SP+2]
				SUB		[SP+1]	;можно и "пожертвовать" значением в Acc,
		;т.к в [SP] лежит точно такое же!
				JL		@@skip
		;дистанция оказалась больше - надо обновить максимум и его индекс
				[SP+1]	[SP]	;двухпортовая память-это зашибись!
				X		j
		@@skip:		jLOOP		@@j_loop
		;по окончании этих циклов, у нас в Y лежит индекс точки, которая является МДД3
		;осталось эту точку поменять местами с точкой под индексом 0...
		;здесь i=j=k=0 (все циклы завершились!)
				i		X
				X		Points2D
				Z		Points2D
				CALL		SwapPoints	;потёрли текущий максимум (лежал в [SP])-и хрен с ним
		
		;на этом первая часть марлезонского балета закончена.
		FindMDD3	endp
	Associate4Points endp

			JMP			[--SP]
AffineAlgorithm 	endp

;меняет местами точку с базой Z, инд. j  и базой X, инд. i
;изменяет регистр k (по окончании выходит 0), и C
SwapPoints	proc
		k		1
@@swap:		C		[Z+2j+k]	;здесь будет HAZARD, использование старого значения k
		[Z+2j+k]	[X+2i+k]
		[X+2i+k]	C
		kLOOP		@@swap
		JMP		[--SP]
SwapPoints	endp	



И прогоним его через транслятор. Получаем следующий лог:

Загружаем файл конфигурации транслятора
Файл конфигурации прочитан, готовы к работе
Обрабатываем файл OurHazardousProgramForFastCPU.asm
Конфликт (Hazard) между командами SP и [SP], процедура main, строки:
		SP		StackAdr
		SP		[SP]		;тут должен быть HAZARD (чтение по адресу из SP, который ещё не записался)
Вставляем NOP

Конфликт (Hazard) между командами i и [Y+2i+k], процедура FindMDD3, строки:
		@@k_loop:	i		3	;от 0 до 1, т.е значения X и Y
		@@i_loop:	Acc		[Y+2i+k]	;тут должен быть HAZARD (обращение по [Y+2i+k] происходит по предыдущему значению i)
Вставляем NOP

Конфликт (Hazard) между командами k и [Z+2j+k], процедура SwapPoints, строки:
		k		1
@@swap:		C		[Z+2j+k]	;здесь будет HAZARD, использование старого значения k
Вставляем NOP

Компиляция завершена успешно
Ширина адреса сегмента кода (и регистра PC):           6   
Ширина адреса сегмента данных (и регистров X,Y,Z,SP):  8   
Количество инициализированных слов данных:             189 
Количество инициализированных слов кода:               36  
Количество адресов процедур:                           2   

Адреса процедур:
AffineAlgorithm= 0005(поле Src = B0) 
SwapPoints=      001D(поле Src = B1) 

Используемые Immediate-значения:
0   (5 раз) 
1   (3 раз) 
3   (2 раз) 
4   (1 раз) 
24  (3 раз) 
-57 (1 раз) 
-17 (1 раз) 
-10 (1 раз) 
-8  (1 раз) 
-6  (1 раз) 
(задействовано 10 из 128)

Используемые адреса Src:
Acc(80)                  2 раз 
C(83)                    1 раз 
j(A1)                    1 раз 
CALL AffineAlgorithm(B0) 1 раз 
CALL SwapPoints(B1)      1 раз 
[X+2i+k](C9)             1 раз 
X(CD)                    1 раз 
[Y+2i+k](D9)             1 раз 
[Y+2j+k](DA)             1 раз 
[Z+2j+k](EA)             1 раз 
[SP+1](F0)               1 раз 
[SP](FC)                 3 раз 
[--SP](FF)               2 раз 
(задействовано 13 из 128)

Используемые адреса Dest:
Acc(80)      1 раз 
ADD(82)      1 раз 
SUB(83)      2 раз 
NOP(89)      3 раз 
C(8A)        1 раз 
SQRD2(9C)    1 раз 
i(A0)        2 раз 
j(A1)        1 раз 
k(A2)        2 раз 
iLOOP(A8)    1 раз 
jLOOP(A9)    1 раз 
kLOOP(AA)    2 раз 
JMP(B0)      3 раз 
JL(B8)       1 раз 
[X+2i+k](C9) 1 раз 
X(CD)        2 раз 
Y(DD)        1 раз 
[Z+2j+k](EA) 1 раз 
Z(ED)        1 раз 
[SP+1](F0)   2 раз 
[SP++](F3)   2 раз 
[SP](FC)     2 раз 
SP(FD)       2 раз 
(задействовано 23 из 256)

Список используемых меток:
a11 =                 00C8 (данные)  
a12 =                 00C9 (данные)  
a13 =                 00CB (данные)
...

(окончание, если кого интересует - под спойлером, там просто все-все метки, в основном из области данных, т.к всю память я когда-то разметил)
[Spoiler (click to open)]
a14 =                 00CE (данные)  
a15 =                 00D2 (данные)  
a16 =                 00D7 (данные)  
a22 =                 00CA (данные)  
a23 =                 00CC (данные)  
a24 =                 00CF (данные)  
a25 =                 00D3 (данные)  
a26 =                 00D8 (данные)  
a33 =                 00CD (данные)  
a34 =                 00D0 (данные)  
a35 =                 00D4 (данные)  
a36 =                 00D9 (данные)  
a44 =                 00D1 (данные)  
a45 =                 00D5 (данные)  
a46 =                 00DA (данные)  
a55 =                 00D6 (данные)  
a56 =                 00DB (данные)  
a66 =                 00DC (данные)  
ADC =                 000E (литерал) 
AffineAlgorithm =     0005 (код)     
AffineMat =           0033 (данные)  
AfMat00 =             0033 (данные)  
AfMat01 =             0034 (данные)  
AfMat02 =             0035 (данные)  
AfMat03 =             0036 (данные)  
AfMat10 =             0037 (данные)  
AfMat11 =             0038 (данные)  
AfMat12 =             0039 (данные)  
AfMat13 =             003A (данные)  
AfMat20 =             003B (данные)  
AfMat21 =             003C (данные)  
AfMat22 =             003D (данные)  
AfMat23 =             003E (данные)  
AfTransf =            00CE (данные)  
Associate4Points =    0005 (код)     
Bz =                  00F7 (данные)  
ChebW =               0032 (данные)  
DistA[0] =            003F (данные)  
DistA[1] =            0040 (данные)  
DistA[10] =           0049 (данные)  
DistA[11] =           004A (данные)  
DistA[12] =           004B (данные)  
DistA[13] =           004C (данные)  
DistA[14] =           004D (данные)  
DistA[15] =           004E (данные)  
DistA[16] =           004F (данные)  
DistA[17] =           0050 (данные)  
DistA[18] =           0051 (данные)  
DistA[19] =           0052 (данные)  
DistA[2] =            0041 (данные)  
DistA[20] =           0053 (данные)  
DistA[21] =           0054 (данные)  
DistA[22] =           0055 (данные)  
DistA[23] =           0056 (данные)  
DistA[24] =           0057 (данные)  
DistA[25] =           0058 (данные)  
DistA[26] =           0059 (данные)  
DistA[27] =           005A (данные)  
DistA[28] =           005B (данные)  
DistA[29] =           005C (данные)  
DistA[3] =            0042 (данные)  
DistA[30] =           005D (данные)  
DistA[31] =           005E (данные)  
DistA[4] =            0043 (данные)  
DistA[5] =            0044 (данные)  
DistA[6] =            0045 (данные)  
DistA[7] =            0046 (данные)  
DistA[8] =            0047 (данные)  
DistA[9] =            0048 (данные)  
ErrCode =             00E2 (данные)  
ETH =                 0002 (литерал) 
Exp =                 00EF (данные)  
FindMDD3 =            0005 (код)     
FindMDD3::@i_loop =   000B (код)     
FindMDD3::@j_loop =   0008 (код)     
FindMDD3::@k_loop =   000A (код)     
FindMDD3::@skip =     0017 (код)     
Fx0 =                 0018 (данные)  
Fx1 =                 001A (данные)  
Fx2 =                 001C (данные)  
Fx3 =                 001E (данные)  
Fx4 =                 0020 (данные)  
Fx5 =                 0022 (данные)  
Fx6 =                 0024 (данные)  
Fx7 =                 0026 (данные)  
Fy0 =                 0019 (данные)  
Fy1 =                 001B (данные)  
Fy2 =                 001D (данные)  
Fy3 =                 001F (данные)  
Fy4 =                 0021 (данные)  
Fy5 =                 0023 (данные)  
Fy6 =                 0025 (данные)  
Fy7 =                 0027 (данные)  
HasData =             00DE (данные)  
K1 =                  00E5 (данные)  
K2 =                  00E6 (данные)  
K3 =                  00E7 (данные)  
K4 =                  00E8 (данные)  
K5 =                  00E9 (данные)  
K6 =                  00EA (данные)  
LCD =                 0001 (литерал) 
LongRangeRefPoints =  00C3 (данные)  
main =                0000 (код)     
main::@endless =      0004 (код)     
ManhW =               0031 (данные)  
Matrix =              00C8 (данные)  
MBD1x =               00A3 (данные)  
MBD1y =               00A4 (данные)  
MBD1z =               00A5 (данные)  
MBD2x =               00A6 (данные)  
MBD2y =               00A7 (данные)  
MBD2z =               00A8 (данные)  
MBD3x =               00A9 (данные)  
MBD3y =               00AA (данные)  
MBD3z =               00AB (данные)  
MBD4x =               00AC (данные)  
MBD4y =               00AD (данные)  
MBD4z =               00AE (данные)  
MBD5x =               00AF (данные)  
MBD5y =               00B0 (данные)  
MBD5z =               00B1 (данные)  
MBD6x =               00B2 (данные)  
MBD6y =               00B3 (данные)  
MBD6z =               00B4 (данные)  
MBD7x =               00B5 (данные)  
MBD7y =               00B6 (данные)  
MBD7z =               00B7 (данные)  
MBD8x =               00B8 (данные)  
MBD8y =               00B9 (данные)  
MBD8z =               00BA (данные)  
MBDx =                00C4 (данные)  
MBDy =                00C5 (данные)  
MBDz =                00C6 (данные)  
MDD1x =               00BE (данные)  
MDD1y =               00BF (данные)  
MDD1z =               00C0 (данные)  
MDD2x =               00C1 (данные)  
MDD2y =               00C2 (данные)  
MDD2z =               00C3 (данные)  
MDD3x =               00BB (данные)  
MDD3y =               00BC (данные)  
MDD3z =               00BD (данные)  
MetricW =             0031 (данные)  
MinusOne =            0001 (литерал) 
MinusThreeHalf =      0000 (литерал) 
OneHalf =             00E3 (данные)  
pad85 =               00ED (данные)  
PixToRad =            0030 (данные)  
Points2D =            0018 (данные)  
QuatA =               00F3 (данные)  
QuatX =               00F4 (данные)  
QuatY =               00F5 (данные)  
QuatZ =               00F6 (данные)  
QValid =              00DF (данные)  
Radius0 =             0016 (данные)  
Radius1 =             0017 (данные)  
RoughPoints =         0000 (данные)  
RoughX0 =             0000 (данные)  
RoughX1 =             0002 (данные)  
RoughX10 =            0014 (данные)  
RoughX2 =             0004 (данные)  
RoughX3 =             0006 (данные)  
RoughX4 =             0008 (данные)  
RoughX5 =             000A (данные)  
RoughX6 =             000C (данные)  
RoughX7 =             000E (данные)  
RoughX8 =             0010 (данные)  
RoughX9 =             0012 (данные)  
RoughY0 =             0001 (данные)  
RoughY1 =             0003 (данные)  
RoughY10 =            0015 (данные)  
RoughY2 =             0005 (данные)  
RoughY3 =             0007 (данные)  
RoughY4 =             0009 (данные)  
RoughY5 =             000B (данные)  
RoughY6 =             000D (данные)  
RoughY7 =             000F (данные)  
RoughY8 =             0011 (данные)  
RoughY9 =             0013 (данные)  
RoundZero =           0003 (литерал) 
Rx =                  00CC (данные)  
Ry =                  00CD (данные)  
SD =                  000A (литерал) 
ShortRangeRefPoints = 00C0 (данные)  
st[1] =               0060 (данные)  
st[2] =               0061 (данные)  
st[3] =               0062 (данные)  
st[4] =               0063 (данные)  
st[5] =               0064 (данные)  
st[6] =               0065 (данные)  
st[7] =               0066 (данные)  
st[8] =               0067 (данные)  
Stack =               005F (данные)  
StackAdr =            00C7 (данные)  
state =               00DD (данные)  
SwapPoints =          001D (код)     
SwapPoints::@swap =   001E (код)     
TargetCnt =           00EC (данные)  
TargetPTR =           00EB (данные)  
ThreeHalf =           0002 (литерал) 
Tx =                  00F0 (данные)  
TxOut =               00EE (данные)  
Txx =                 00CE (данные)  
Txx' =                00C8 (данные)  
Txy =                 00D0 (данные)  
Txy' =                00CA (данные)  
Ty =                  00F1 (данные)  
Tyx =                 00CF (данные)  
Tyx' =                00C9 (данные)  
Tyy =                 00D1 (данные)  
Tyy' =                00CB (данные)  
Tz =                  00F2 (данные)  
UART =                0000 (литерал) 
Vel =                 00E1 (данные)  
VValid =              00E0 (данные)  
W0 =                  0028 (данные)  
W1 =                  0029 (данные)  
W2 =                  002A (данные)  
W3 =                  002B (данные)  
W4 =                  002C (данные)  
W5 =                  002D (данные)  
W6 =                  002E (данные)  
W7 =                  002F (данные)  
ZeroInv =             00E4 (данные)  



Действительно, транслятор нашёл Hazard'ы там, где мы их ждали, и не нашёл там, где не надо! Скажем, в строках

CALL AffineAlgorithm
JMP  [--SP]

он мог бы найти Hazard, поскольку они транслируются в

[SP++]  CALL0
JMP     [--SP]


а при сдвиге всего левого столбца вниз получаем пару:
[SP++]  [--SP]

что явно криминал.

Но, у нас срабатывает условие PrevSrc.CreatesBubble: вызов процедуры заставляет не исполнять одновременно [SP++] и [--SP] (последний выкидывается), а когда управление вернётся к строке JMP [--SP], предыдущая команда DestAddr будет "выкинута", поэтому конфликта заведомо не будет.

Посмотрим, какой у нас получился листинг:

main proc
00  FD47              SP      StackAdr
01  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
02  FDFC              SP      [SP]        ;тут должен быть HAZARD (чтение по адресу из SP, который ещё не записался)
03  F3B0              CALL        AffineAlgorithm
04  B004  @@endless:  JMP     @@endless
main endp
AffineAlgorithm     proc
    Associate4Points    proc
        FindMDD3    proc
05  DD18                      Y       Points2D
06  F000                      [SP+1]  0   ;максимальная отдалённость, инициализируем нулём
07  A103                      j       3
08  A201          @@j_loop:   k       1   ;также от 0 до 3, чтобы все расстояния просуммировать
09  FC00                      [SP]    0   ;здесь будет храниться текущий максимум
0A  A003          @@k_loop:   i       3   ;от 0 до 1, т.е значения X и Y
0B  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
0C  80D9          @@i_loop:   Acc     [Y+2i+k]    ;тут должен быть HAZARD (обращение по [Y+2i+k] происходит по предыдущему значению i)
0D  83DA                      SUB     [Y+2j+k]    ;вычитаем второе
0E  9C80                      SQRD2   Acc         ;возводим в квадрат
0F  82FC                      ADD     [SP]        ;прибавляем к пред. значению
10  FC80                      [SP]    Acc
11  A879                      iLOOP   @@i_loop        ;теперь то же самое для второй координаты
12  AA76                      kLOOP   @@k_loop
13  83F0                      SUB     [SP+1]  ;можно и "пожертвовать" значением в Acc,
14  B801                      JL      @@skip
15  F0FC                      [SP+1]  [SP]    ;двухпортовая память-это зашибись!
16  CDA1                      X       j
17  A96F          @@skip:     jLOOP   @@j_loop
18  A0CD                      i       X
19  CD18                      X       Points2D
1A  ED18                      Z       Points2D
1B  F3B1                      CALL    SwapPoints  ;потёрли текущий максимум (лежал в [SP])-и хрен с ним
        FindMDD3    endp
    Associate4Points endp
1C  B0FF              JMP         [--SP]
AffineAlgorithm     endp
SwapPoints  proc
1D  A201              k           1
1E  8900      NOP  0 ;AUTOMATICALLY INSERTED BY TRANSLATOR TO PREVENT HAZARD
1F  8AEA  @@swap:     C           [Z+2j+k]    ;здесь будет HAZARD, использование старого значения k
20  EAC9              [Z+2j+k]    [X+2i+k]
21  C983              [X+2i+k]    C
22  AA7B              kLOOP       @@swap
23  B0FF              JMP         [--SP]
SwapPoints  endp       


Всё верно. Пришлось поставить небольшой костыль (нижние 2 строки в листинге куска программы, отвечающего за Hazard'ы), чтобы и метка сдвигалась на единицу вниз вместе с самой командой. Понятное дело, что метка записывалась ещё перед анализом самой команды, и без этих строк она так и указывала бы на NOP. В этом нет большой проблемы - лишний раз выполнится команда "ничего не делать", но всё-таки нехорошо.

Костыль - потому что по-хорошему надо было сделать чуть лучше. Синтаксис допускает сколько угодно меток, вроде такого:

    loop:  
    cycle:
    cmd10:
    begin:  k   1


и все метки будут направлять на одну и ту же команду. Сейчас получается, что если туда вклинился NOP, только последняя метка, begin:, сдвинется на единицу, а остальные будут указывать на NOP. Я ещё ни разу не использовал такое в сегменте кода (разве что вложенные процедуры, которые тоже являются метками, но между процедурами не должны попаться Hazard'ы), только в сегменте данных, чтобы обозначить и массив целиком, и его первый элемент. Но туда NOPы вставлять не требуется :)

Похоже, что всё хорошо. На очереди - тестирование на симуляторе, сначала этой программы, а потом нарастим её до целого аффинного алгоритма.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Я создал монстра!

    Вот нормальная счастливая пара разъёмов ОНЦ-БС-1-10/14-Р12-2-В и ОНЦ-БС-1-10/14-В1-2-В: У розетки кроме основного выступа, отмечающего "верх",…

  • Нахождение двух самых отдалённых точек

    Пока компьютер долго и упорно мучал симуляцию, я пытался написать на ассемблере алгоритм захвата на ближней дистанции. А сейчас на этом коде можно…

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments