Рубрики

ВОРОТА | GATE CS 2010 | Вопрос 37

Программа ниже использует шесть временных переменных a, b, c, d, e, f.

 
    a = 1
    b = 10
    c = 20
    d = a+b
    e = c+d
    f = c+e
    b = c+e
    e = b+f
    d = 5+e
    return d+f

Предполагая, что все операции берут свои операнды из регистров, какое минимальное количество регистров необходимо для выполнения этой программы без разливов?
(А) 2
(Б) 3
(С) 4
(D) 6

Ответ: (Б)
Объяснение: Все приведенные выражения используют не более 3 переменных, поэтому мы никогда не должны иметь более 3 регистров.

Смотрите http://en.wikipedia.org/wiki/Register_allocation

Требуется минимум 3 регистра.

Принцип распределения регистров : если переменная должна быть назначена регистру, система проверяет наличие любого свободного регистра, если он его находит, он выделяет. Если нет свободного регистра, то он проверяет регистр, который содержит мертвую переменную (переменную, значение которой не будет использоваться в будущем), и, если он ее найдет, он выделяет. В противном случае он выполняет Spilling (он проверяет регистр, значение которого требуется после самого длительного времени, сохраняет его значение в памяти, а затем использует этот регистр для текущего выделения, а затем, когда требуется старое значение регистра, система получает это из памяти, где он был сохранен и распределить его в любом доступном регистре).

Но здесь мы не должны применять разлив, как указано в вопросе.

Давайте выделим регистры для переменных.

a = 1 (скажем, регистр R1 выделен для переменной 'a')

b = 10 (R2 для «b», потому что значение «a» будет использоваться в будущем, поэтому не может заменить переменную «a» на переменную «b» в R1)

c = 20 (R3 для «c», потому что значения «a» и «b» будут использоваться в будущем, поэтому не могут заменить переменную «a» или «b» на «c» в R1 или R2 соответственно )

d = a + b (теперь 'd' может быть назначено для R1, потому что R1 содержит мертвую переменную, которая является 'a', и это так называется, потому что она не будет использоваться в будущем, то есть никакое последующее выражение не использует значение переменная «а»)

e = c + d ('e' может быть назначено для R1, потому что в настоящее время R1 содержит значение переменной 'd', которая не будет использоваться в последующем выражении.)

Примечание : уже вычисленное значение переменной используется только операцией READ (не WRITE), поэтому мы должны видеть только на стороне RHS последующих выражений, будет ли переменная использоваться или нет.

f = c + e ('f' может быть назначено для R2, потому что поле 'b' в регистре R2 не будет использоваться в последующих выражениях, следовательно, R2 можно использовать для выделения для 'f', заменяя 'b')

b = c + e ('b' может быть назначено для R3, потому что значение 'c' в R3 не используется позже)

e = b + f (здесь 'e' уже в R1, поэтому здесь нет распределения, прямое назначение)

Рекомендуемые посты:

ВОРОТА | GATE CS 2010 | Вопрос 37

0.00 (0%) 0 votes