Математики, ау!

[spamsink]

Вот пишете вы, скажем, компилятор — для простоты, ассемблер — с языка, в котором бывают литеральные константы (не таков был покойный Марк Германович Чайковский).

Как вы организуете уникальность литеральных констант? Посмотрим на БЕМШ и попробуем в нём тест

OШИБKИ   HПK  CBOБ ПEPEM AДPEC KOMAHДA    A ИCП N ГEH N ИCX METKA  OПEPAЦИЯ OПEPAHД   KOMMEHTAPИЙ
                                                 0001  0001 TEST   START 1
         001             00001 00 010 0005       0002  0002        XTA   =B’4’
                               00 010 0006       0003  0003        XTA   =B’1’
                         00002 00 010 0007       0004  0004        XTA   =B’7’
                               00 010 0010       0005  0005        XTA   =B’3’
                         00003 00 010 0011       0006  0006        XTA   =B’6’
                               00 010 0012       0007  0007        XTA   =B’2’
                         00004 00 010 0013       0008  0008        XTA   =B’5’
                               00 22
                                                 0009  0009        FIN
                         00005  0000000000000004
                         00006  0000000000000001
         002             00007  0000000000000007
                         00010  0000000000000003
                         00011  0000000000000006
                         00012  0000000000000002
                         00013  0000000000000005

Как видим, в каком порядке литералы были упомянуты в коде, в таком и получились в блоке данных. Если разных литералов не безумные тыщи, то цикл линейного поиска, помещающийся в БРС, вполне адекватен, и добавление нового литерала в конец массива не требует копирования памяти.

А теперь попробуем Мадлен:

                         TEST    :  , NAME,
 000000010 4001                     , XTA ,=4
  -  00010 4002                     , XTA ,=1
 000100010 4003                     , XTA ,=7
  -  00010 4004                     , XTA ,=3
 000200010 4005                     , XTA ,=6
  -  00010 4006                     , XTA ,=2
 000300010 4007                     , XTA ,=5
  -  0022 00000
 0004 0000 0000 0000 0001
 0005 0000 0000 0000 0002
 0006 0000 0000 0000 0003
 0007 0000 0000 0000 0004
 0010 0000 0000 0000 0005
 0011 0000 0000 0000 0006
 0012 0000 0000 0000 0007
                                    , END ,

О, так Мадлен просто сортирует литералы по возрастанию! А нет ли у него проблем с нетранзитивностью сравнения с помощью циклического сложения? Ну-ка,

                         TEST    :  , NAME,
 000000010 4001                     , XTA ,=4
  -  00010 4002                     , XTA ,=1
 000100010 4003                     , XTA ,=7
  -  00010 4004                     , XTA ,=3
 000200010 4005                     , XTA ,=4000 0000 0000 0001
  -  00010 4006                     , XTA ,=4000 0000 0000 0000
 000300010 4007                     , XTA ,=3777 7777 7777 7777
  -  00010 4010                     , XTA ,=0
 000400010 4011                     , XTA ,=6
  -  00010 4012                     , XTA ,=2
 000500010 4013                     , XTA ,=5
  -  00010 4005                     , XTA ,=4000 0000 0000 0001
 000600010 4006                     , XTA ,=4000 0000 0000 0000
  -  00010 4007                     , XTA ,=3777 7777 7777 7777
 000700010 4010                     , XTA ,=0
  -  0022 00000
 0010 0000 0000 0000 0000
 0011 0000 0000 0000 0001
 0012 0000 0000 0000 0002
 0013 0000 0000 0000 0003
 0014 0000 0000 0000 0004
 0015 0000 0000 0000 0005
 0016 0000 0000 0000 0006
 0017 3777 7777 7777 7777
 0020 0000 0000 0000 0007
 0021 4000 0000 0000 0000
 0022 4000 0000 0000 0001
                                    , END ,

Константы не дублируются, уже хорошо, но порядок констант уже непонятен. Попробуем так:

                         TEST    :  , NAME,
 000000010 4001                     , XTA ,=4
  -  00010 4002                     , XTA ,=1
 000100010 4003                     , XTA ,=7
  -  00010 4004                     , XTA ,=3
 000200010 4005                     , XTA ,=6
  -  00010 4006                     , XTA ,=2
 000300010 4007                     , XTA ,=5
  -  00010 4010                     , XTA ,=I4
 000400010 4011                     , XTA ,=I1
  -  00010 4012                     , XTA ,=I7
 000500010 4013                     , XTA ,=I3
  -  00010 4014                     , XTA ,=I6
 000600010 4015                     , XTA ,=I2
  -  00010 4016                     , XTA ,=I5
 0007 6400 0000 0000 0003
 0010 0000 0000 0000 0001
 0011 6400 0000 0000 0004
 0012 0000 0000 0000 0002
 0013 6400 0000 0000 0005
 0014 0000 0000 0000 0003
 0015 6400 0000 0000 0006
 0016 0000 0000 0000 0004
 0017 6400 0000 0000 0007
 0020 0000 0000 0000 0005
 0021 0000 0000 0000 0006
 0022 0000 0000 0000 0007
 0023 6400 0000 0000 0001
 0024 6400 0000 0000 0002

Полученный порядок такой: I3, 1, I4, 2, I5, 3, I6, 4, I7, 5, 6, 7, I1, I2.

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

Comments

[spamsink]

Идентичные литеральные константы разных типов не совмещались намеренно (это даже упомянуто в инструкции):

                         TEST    :  , NAME,
 000000010 4001                     , XTA ,=:64
  -  00010 4002                     , XTA ,=I0
 000100010 4003                     , XTA ,=6H’320’’’’’’’’’’’
  -  0022 00000
 0002 6400 0000 0000 0000
 0003 6400 0000 0000 0000
 0004 6400 0000 0000 0000

[vak]

В юниксном ассемблере для БЭСМ-6 я завёл отдельную секцию для литералов. Секция размещалась в "короткой" памяти. Все такие секции линкер объединял в одну и сливал повторяющиеся константы, для экономии памяти.

[spamsink]

Это красиво. Кстати, удивительно, что в Дубне не поместили больше частых литералов в резидент (или даже ниже резидента). Взять те же с М47В'1' по В'1', как это было сделано в Диспаке - много кода можно было бы сэкономить, а то чуть не в каждой процедуре есть своя личная константа В'1'.