MipsRegisterAllocMiddleware.java 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250
  1. /*
  2. * To change this license header, choose License Headers in Project Properties.
  3. * To change this template file, choose Tools | Templates
  4. * and open the template in the editor.
  5. */
  6. package targets.mips;
  7. import API.Api;
  8. import API.MiddlewareInterface;
  9. import common.AllocatorInterface;
  10. import common.Code;
  11. import common.Instruction;
  12. import java.util.LinkedHashMap;
  13. import java.util.LinkedList;
  14. import middlewares.BasicBlockMiddleware;
  15. import middlewares.BlockBaseGroup;
  16. import middlewares.BlockBaseOcorrences;
  17. import middlewares.Interval;
  18. /**
  19. *
  20. * @author EUGENIO CARVALHO
  21. */
  22. public class MipsRegisterAllocMiddleware implements AllocatorInterface, MiddlewareInterface {
  23. protected int instructionPosition;
  24. protected Code tac;
  25. protected Registers registers;
  26. protected BlockBaseGroup group;
  27. protected LinkedList<String> free = new LinkedList<>();
  28. protected BasicBlockMiddleware blockProcessor;
  29. protected String[] withoutRegister = "jump,call,return".split(",");
  30. public MipsRegisterAllocMiddleware() {
  31. }
  32. @Override
  33. public void Exec(Code c, LinkedHashMap<String, MiddlewareInterface> cp) throws Exception {
  34. BlockBaseOcorrences bb;
  35. System.out.println("AllocatorMipsProcessor:");
  36. Code IR = c.Parent;
  37. String blockname = c.Block().getName();
  38. IR.Use(blockname);
  39. registers = new Registers();
  40. blockProcessor = (BasicBlockMiddleware) cp.get("ir.basic.blocks");
  41. instructionPosition = 0;
  42. group = blockProcessor.getBasicBlockGroup(IR.Block().getName());
  43. group.Init();
  44. for (Instruction inst : IR.Block().Instructions()) {
  45. // ignora se a instrução for do tipo controle
  46. if (inst.in("type", IR.ControlInstructions)) {
  47. continue;
  48. }
  49. // Se a instrução possui enderecamento de registradores
  50. if (!inst.in("type", withoutRegister)) {
  51. // Se a instruncao pertence ao proximo bloco basico atualiza o grupo
  52. bb = group.getBasicBlocks(1);
  53. // System.out.println("###ASSIGN:(" + instructionPosition + ")(" + group.getBasicBlocks(1).getLeader() + ")");
  54. if (bb != null && instructionPosition >= bb.getLeader()) {
  55. group.NextBlock();
  56. // System.out.println(">>>>> Mudei para bloco basico:" + group.Current().getName());
  57. }
  58. // Libera registradores alocados temporariamente
  59. while (!free.isEmpty()) {
  60. registers.Free(free.pop());
  61. }
  62. // Atribui os registradores a instrucao
  63. Assign(inst);
  64. }
  65. // Incrimenta o ponteiro para a proxima instrucao
  66. instructionPosition++;
  67. }
  68. // System.out.println(group);
  69. }
  70. @Override
  71. public void Alloc(Code code) {
  72. this.tac = code;
  73. }
  74. protected void Assign(Instruction inst) throws Exception {
  75. // System.out.println("Assign:" + inst.Get("type") + ":" + inst.Get("local.position"));
  76. String reg;
  77. String[] opDeslocamento = "<<,>>".split(",");
  78. for (String param : new String[]{"p1", "p2", "dst.indice", "p1.indice"}) {
  79. if (!inst.Has(param) || ((inst.in("op", opDeslocamento) && param.equals("p2")))) {
  80. continue;
  81. }
  82. // System.out.println("PARAM:[" + param + "value" + "]" + x.eq(param + "value", "true"));
  83. // if (!x.in("op", opDeslocamento)) {
  84. // } else
  85. if (inst.eq(param + "value", "true") || inst.isNumber(param)) {
  86. reg = registers.Lock("t");
  87. free.push(reg);
  88. Load(inst, param);
  89. } else {
  90. // System.out.println("GX:" + param + "->" + x);
  91. reg = GetRegister(inst, param);
  92. }
  93. inst.Set("reg." + param, reg);
  94. // System.out.println("Assign:[" + param + "]" + inst);
  95. }
  96. if (inst.Has("dst")) {
  97. inst.Set("reg.dst", GetRegister(inst, "dst"));
  98. }
  99. }
  100. protected void Load(Instruction x, String param) {
  101. x.Set("reg." + param + ".load", "true");
  102. }
  103. protected String GetRegister(Instruction x, String address) throws Exception {
  104. BlockBaseOcorrences bb = group.Current();
  105. String reg, addr = bb.ToAliase(x, address);
  106. int position = x.GetInt("block.position"), leader = bb.getLeader();
  107. // Corrige a posicao para iniciar de 0 para cada bloco basico referente ao lider de cada bloco.
  108. position = (leader == 0) ? position : position - leader;
  109. boolean dst = address.equals("dst");
  110. // System.out.println("GetRegister: (" + address + "):(" + addr + ") : ["
  111. // + instructionPosition
  112. // + " : "
  113. // + position
  114. // + " : "
  115. // + leader + "]");
  116. // System.out.println(x);
  117. Interval interval = bb.Get(addr, position);
  118. // System.out.println(bb);
  119. // System.out.println(interval);
  120. // System.out.println("}");
  121. // Define um registrador se não possuir um definido no intervalo
  122. if (!interval.RegisterDefined()) {
  123. // System.out.println("Não tinha definido: Carregar da memoria(" + (!dst) + ")");
  124. // Verifica a existencia de um registrador disponivel
  125. reg = AvaliableRegister(addr);
  126. // System.out.println("[" + dst + "]GerRegister não definido: (" + address + ")/add: " + addr);
  127. if (!dst) {
  128. // Parametro define que o valor deve ser carregado em registrador;
  129. Load(x, address);
  130. }
  131. // Libera um registrador ocupado
  132. if (reg == null) {
  133. // System.out.println("spill" + bb + " P:" + position + " b:" + bb.Spill(position));
  134. reg = bb.Spill(position).getRegister();
  135. }
  136. // Vincula o registrador com o intervalo
  137. interval.setRegister(reg);
  138. } else {
  139. reg = interval.getRegister();
  140. // Se escreve no registrador e não é o ultimo intervalo marca para
  141. // ser salvo marca para ser salvo.
  142. // if (dst && !group.Last(addr).equals(interval)) {
  143. // Libera o registrador
  144. // System.out.println("Tinha definido::" + reg + ":Liberadp{" + addr + "}:" + (interval.End == position));
  145. }
  146. if (dst) {
  147. interval.Perisist(true);
  148. }
  149. // Se for
  150. // -> A ultima ocorrencia do intervalo e
  151. // -> O registrador é saved e
  152. // -> Ocorreu escrita no registrador
  153. // -> Ponteiros e variaveis globais devem persistidas apos cada operacao de escrita
  154. // marca para gravar em memoria
  155. if (interval.End == position) {
  156. registers.Free(reg);
  157. // System.out.println("reg(" + reg + ")persist(" + interval.Perisist() + ")");
  158. if (reg.substring(0, 1).equals("s")
  159. && interval.Perisist()) {
  160. x.Set("reg." + address + ".store", "true");
  161. }
  162. }
  163. // System.out.println("}" + reg + "::" + position);
  164. return reg;
  165. }
  166. protected String AvaliableRegister(String alias) throws Exception {
  167. String reg = "";
  168. switch (Api.clearID(alias).substring(1, 2)) {
  169. case "V":
  170. case "G":
  171. reg = "s";
  172. break;
  173. case "T":
  174. case "C":
  175. reg = "t";
  176. break;
  177. default:
  178. throw new Exception(String.format("Not avaliable register to alias '%s'", alias));
  179. }
  180. return registers.Lock(reg);
  181. }
  182. protected String PopReturnRegister() {
  183. return null;
  184. }
  185. @Override
  186. public void Get(String id, int position) {
  187. throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
  188. }
  189. }
  190. //leadersList:[0, 3, 7, 8]
  191. // : <bitCount>:
  192. //13: 0: pop_param _V4 T< pop_param >
  193. //14: 1: _V5 := 0 T< copy >
  194. //15: 2: if _V4 <= 0 goto <bitCount+_i4> T< branch >
  195. // : <bitCount+_i6>:
  196. //16: 3: _V5 := _V5 + 1 T< assign >
  197. //17: 4: _T6 := _V4 - 1 T< assign >
  198. //18: 5: _V4 := _V4 & _T6 T< assign >
  199. //19: 6: if _V4 == 0 goto <bitCount+_i7> T< branch >
  200. //20: 7: goto <bitCount+_i6> T< jump >
  201. // : <bitCount+_i7>:
  202. // : <bitCount+_i4>:
  203. //21: 8: push_return _V5 T< push_return >
  204. //22: 9: return 1 T< return >
  205. // : <bitCount-end>: