1 // Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2010 - 2011
2 //
3 // (c) 2010-2012 Goethe-Universität Frankfurt
4 //
5 // This program is free software; you can redistribute it and/or modify it
6 // under the terms of the GNU General Public License as published by the
7 // Free Software Foundation; either version 2, or (at your option) any
8 // later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software
17 // Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 //
19 // An optimal, polynomial-time register allocator.
20
21 // #define DEBUG_RALLOC_DEC // Uncomment to get debug messages while doing register allocation on the tree decomposition.
22 // #define DEBUG_RALLOC_DEC_ASS // Uncomment to get debug messages about assignments while doing register allocation on the tree decomposition (much more verbose than the one above).
23
24 #include "SDCCralloc.hpp"
25 #include "SDCCsalloc.hpp"
26
27 extern "C"
28 {
29 #include "z80.h"
30 unsigned char dryZ80iCode (iCode * ic);
31 bool z80_assignment_optimal;
32 bool should_omit_frame_ptr;
33 }
34
35 #define REG_A 0
36 #define REG_C 1
37 #define REG_B 2
38 #define REG_E 3
39 #define REG_D 4
40 #define REG_L 5
41 #define REG_H 6
42 #define REG_IYL 7
43 #define REG_IYH 8
44
45 template <class G_t, class I_t>
default_operand_cost(const operand * o,const assignment & a,unsigned short int i,const G_t & G,const I_t & I)46 float default_operand_cost(const operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
47 {
48 float c = 0.0f;
49
50 operand_map_t::const_iterator oi, oi_end;
51
52 var_t byteregs[4]; // Todo: Change this when sdcc supports variables larger than 4 bytes in registers.
53 unsigned short int size;
54
55 if(o && IS_SYMOP(o))
56 {
57 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key);
58 if(oi != oi_end)
59 {
60 var_t v = oi->second;
61
62 // In registers.
63 if(std::binary_search(a.local.begin(), a.local.end(), v))
64 {
65 c += 1.0f;
66 byteregs[I[v].byte] = a.global[v];
67 size = 1;
68
69 while(++oi != oi_end)
70 {
71 v = oi->second;
72 c += (std::binary_search(a.local.begin(), a.local.end(), v) ? 1.0f : std::numeric_limits<float>::infinity());
73 byteregs[I[v].byte] = a.global[v];
74 size++;
75 }
76
77 // Penalty for not placing 2- and 4-byte variables in register pairs
78 // Todo: Extend this once the register allcoator can use registers other than bc, de:
79 if ((size == 2 || size == 4) &&
80 (byteregs[1] != byteregs[0] + 1 || (byteregs[0] != REG_C && byteregs[0] != REG_E && byteregs[0] != REG_L)))
81 c += 2.0f;
82 if (size == 4 &&
83 (byteregs[3] != byteregs[2] + 1 || (byteregs[2] != REG_C && byteregs[2] != REG_E && byteregs[0] != REG_L)))
84 c += 2.0f;
85
86 // Code generator cannot handle variables only partially in A.
87 if(size > 1)
88 for(unsigned short int i = 0; i < size; i++)
89 if(byteregs[i] == REG_A)
90 c += std::numeric_limits<float>::infinity();
91
92 if(byteregs[0] == REG_A)
93 c -= 0.4f;
94 else if(OPTRALLOC_HL && byteregs[0] == REG_L)
95 c -= 0.1f;
96 else if((OPTRALLOC_IY && byteregs[0] == REG_IYL) || byteregs[0] == REG_IYH)
97 c += 0.1f;
98 }
99 // Spilt.
100 else
101 {
102 c += OP_SYMBOL_CONST(o)->remat ? 1.5f : 4.0f;
103 while(++oi != oi_end)
104 {
105 v = oi->second;
106 c += (!std::binary_search(a.local.begin(), a.local.end(), v) ? 4.0f : std::numeric_limits<float>::infinity());
107 }
108 }
109 }
110 }
111
112 return(c);
113 }
114
115 // Check that the operand is either fully in registers or fully in memory.
116 template <class G_t, class I_t>
operand_sane(const operand * o,const assignment & a,unsigned short int i,const G_t & G,const I_t & I)117 static bool operand_sane(const operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
118 {
119 if(!o || !IS_SYMOP(o))
120 return(true);
121
122 operand_map_t::const_iterator oi, oi_end;
123 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key);
124
125 if(oi == oi_end)
126 return(true);
127
128 // In registers.
129 if(std::binary_search(a.local.begin(), a.local.end(), oi->second))
130 {
131 while(++oi != oi_end)
132 if(!std::binary_search(a.local.begin(), a.local.end(), oi->second))
133 return(false);
134 }
135 else
136 {
137 while(++oi != oi_end)
138 if(std::binary_search(a.local.begin(), a.local.end(), oi->second))
139 return(false);
140 }
141
142 return(true);
143 }
144
145 template <class G_t, class I_t>
default_instruction_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)146 static float default_instruction_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
147 {
148 float c = 0.0f;
149
150 const iCode *ic = G[i].ic;
151
152 c += default_operand_cost(IC_RESULT(ic), a, i, G, I);
153 c += default_operand_cost(IC_LEFT(ic), a, i, G, I);
154 c += default_operand_cost(IC_RIGHT(ic), a, i, G, I);
155
156 return(c);
157 }
158
159 template <class G_t, class I_t>
inst_sane(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)160 static bool inst_sane(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
161 {
162 const iCode *ic = G[i].ic;
163
164 // for a sequence of built-in SENDs, all of the SENDs must be sane
165 if (ic->op == SEND && ic->builtinSEND && ic->next->op == SEND && !inst_sane(a, *(adjacent_vertices(i, G).first), G, I))
166 return(false);
167
168 return(operand_sane(IC_RESULT(ic), a, i, G, I) && operand_sane(IC_LEFT(ic), a, i, G, I) && operand_sane(IC_RIGHT(ic), a, i, G, I));
169 }
170
171 // Treat assignment separately to handle coalescing.
172 template <class G_t, class I_t> static float
assign_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)173 assign_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
174 {
175 float c = 0.0f;
176
177 const iCode *ic = G[i].ic;
178
179 const operand *right = IC_RIGHT(ic);
180 const operand *result = IC_RESULT(ic);
181
182 if(!right || !IS_SYMOP(right) || !result || !IS_SYMOP(result) || POINTER_GET(ic) || POINTER_SET(ic))
183 return(default_instruction_cost(a, i, G, I));
184
185 reg_t byteregs[4] = {-1, -1, -1, -1}; // Todo: Change this when sdcc supports variables larger than 4 bytes in register allocation for z80.
186
187 operand_map_t::const_iterator oi, oi_end;
188
189 int size1 = 0, size2 = 0;
190
191 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(right)->key);
192 if(oi != oi_end)
193 {
194 var_t v = oi->second;
195
196 if(!std::binary_search(a.local.begin(), a.local.end(), v))
197 return(default_instruction_cost(a, i, G, I));
198
199 c += 1.0f;
200 byteregs[I[v].byte] = a.global[v];
201 size1 = 1;
202
203 while(++oi != oi_end)
204 {
205 v = oi->second;
206 c += (std::binary_search(a.local.begin(), a.local.end(), v) ? 1.0f : std::numeric_limits<float>::infinity());
207 byteregs[I[v].byte] = a.global[v];
208 size1++;
209 }
210
211 // Code generator cannot handle variables only partially in A.
212 if(size1 > 1)
213 for(unsigned short int i = 0; i < size1; i++)
214 if(byteregs[i] == REG_A)
215 c += std::numeric_limits<float>::infinity();
216
217 if(byteregs[0] == REG_A)
218 c -= 0.4f;
219 else if((OPTRALLOC_IY && byteregs[0] == REG_IYL) || byteregs[0] == REG_IYH)
220 c += 0.1f;
221 }
222
223 if(!size1)
224 return(default_instruction_cost(a, i, G, I));
225
226 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(result)->key);
227 if(oi != oi_end)
228 {
229 var_t v = oi->second;
230
231 if(!std::binary_search(a.local.begin(), a.local.end(), v))
232 return(default_instruction_cost(a, i, G, I));
233
234 c += 1.0f;
235 if(byteregs[I[v].byte] == a.global[v])
236 c -= 2.0f;
237 size2 = 1;
238
239 while(++oi != oi_end)
240 {
241 v = oi->second;
242 c += (std::binary_search(a.local.begin(), a.local.end(), v) ? 1.0f : std::numeric_limits<float>::infinity());
243 if(byteregs[I[v].byte] == a.global[v])
244 c -= 2.0f;
245 size2++;
246 }
247
248 if(byteregs[0] == REG_A)
249 c -= 0.4f;
250 else if((OPTRALLOC_IY && byteregs[0] == REG_IYL) || byteregs[0] == REG_IYH)
251 c += 0.1f;
252 }
253
254 if(!size2)
255 return(default_instruction_cost(a, i, G, I));
256
257 return(c);
258 }
259
260 template <class G_t, class I_t> static float
return_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)261 return_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
262 {
263 float c = 0.0f;
264
265 const iCode *ic = G[i].ic;
266
267 const operand *left = IC_LEFT(ic);
268
269 if(!left || !IS_SYMOP(left))
270 return(default_instruction_cost(a, i, G, I));
271
272 reg_t byteregs[4] = {-1, -1, -1, -1}; // Todo: Change this when sdcc supports variables larger than 4 bytes.
273
274 operand_map_t::const_iterator oi, oi_end;
275
276 int size = 0;
277
278 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(left)->key);
279 if(oi != oi_end)
280 {
281 var_t v = oi->second;
282
283 if(!std::binary_search(a.local.begin(), a.local.end(), v))
284 return(default_instruction_cost(a, i, G, I));
285
286 c += 1.0f;
287 byteregs[I[v].byte] = a.global[v];
288 size = 1;
289
290 while(++oi != oi_end)
291 {
292 v = oi->second;
293 c += (std::binary_search(a.local.begin(), a.local.end(), v) ? 1.0f : std::numeric_limits<float>::infinity());
294 byteregs[I[v].byte] = a.global[v];
295 size++;
296 }
297
298 if(byteregs[0] == REG_A)
299 c -= 0.4f;
300
301 if(byteregs[0] == REG_L)
302 c -= 1.0f;
303 if(byteregs[1] == REG_H)
304 c -= 1.0f;
305 if(byteregs[2] == REG_E)
306 c -= 1.0f;
307 if(byteregs[3] == REG_D)
308 c -= 1.0f;
309 }
310
311 return(c);
312 }
313
314 template <class G_t, class I_t> static float
call_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)315 call_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
316 {
317 float c = 0.0f;
318
319 const iCode *ic = G[i].ic;
320
321 const operand *result = IC_RESULT(ic);
322
323 if(!result || !IS_SYMOP(result))
324 return(default_instruction_cost(a, i, G, I));
325
326 reg_t byteregs[4] = {-1, -1, -1, -1}; // Todo: Change this when sdcc supports variables larger than 4 bytes.
327
328 operand_map_t::const_iterator oi, oi_end;
329
330 int size = 0;
331
332 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(result)->key);
333 if(oi != oi_end)
334 {
335 var_t v = oi->second;
336
337 if(!std::binary_search(a.local.begin(), a.local.end(), v))
338 return(default_instruction_cost(a, i, G, I));
339
340 c += 1.0f;
341 byteregs[I[v].byte] = a.global[v];
342 size = 1;
343
344 while(++oi != oi_end)
345 {
346 v = oi->second;
347 c += (std::binary_search(a.local.begin(), a.local.end(), v) ? 1.0f : std::numeric_limits<float>::infinity());
348 byteregs[I[v].byte] = a.global[v];
349 size++;
350 }
351
352 // Code generator cannot handle variables only partially in A.
353 if(size > 1)
354 for(unsigned short int i = 0; i < size; i++)
355 if(byteregs[i] == REG_A)
356 c += std::numeric_limits<float>::infinity();
357
358 if(byteregs[0] == REG_A)
359 c -= 0.4f;
360
361 if(byteregs[0] == REG_L)
362 c -= 1.0f;
363 if(byteregs[1] == REG_H)
364 c -= 1.0f;
365 if(byteregs[2] == REG_E)
366 c -= 1.0f;
367 if(byteregs[3] == REG_D)
368 c -= 1.0f;
369 }
370
371 return(c);
372 }
373
374 template <class G_t, class I_t> static float
ifx_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)375 ifx_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
376 {
377 const iCode *ic = G[i].ic;
378
379 return(default_operand_cost(IC_COND(ic), a, i, G, I));
380 }
381
382 template <class G_t, class I_t> static float
jumptab_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)383 jumptab_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
384 {
385 const iCode *ic = G[i].ic;
386
387 return(default_operand_cost(IC_JTCOND(ic), a, i, G, I));
388 }
389
390 template <class I_t>
add_operand_conflicts_in_node(const cfg_node & n,I_t & I)391 static void add_operand_conflicts_in_node(const cfg_node &n, I_t &I)
392 {
393 const iCode *ic = n.ic;
394
395 const operand *result = IC_RESULT(ic);
396 const operand *left = IC_LEFT(ic);
397 const operand *right = IC_RIGHT(ic);
398
399 if(!result || !IS_SYMOP(result))
400 return;
401
402 if(!(ic->op == UNARYMINUS || ic->op == '+' || ic->op == '-' || ic->op == '^' || ic->op == '|' || ic->op == BITWISEAND))
403 return; // Code generation can always handle all other operations. Todo: Handle ^, |, BITWISEAND and float UNARYMINUS there as well.
404
405 operand_map_t::const_iterator oir, oir_end, oirs;
406 boost::tie(oir, oir_end) = n.operands.equal_range(OP_SYMBOL_CONST(result)->key);
407 if(oir == oir_end)
408 return;
409
410 operand_map_t::const_iterator oio, oio_end;
411
412 if(left && IS_SYMOP(left))
413 for(boost::tie(oio, oio_end) = n.operands.equal_range(OP_SYMBOL_CONST(left)->key); oio != oio_end; ++oio)
414 for(oirs = oir; oirs != oir_end; ++oirs)
415 {
416 var_t rvar = oirs->second;
417 var_t ovar = oio->second;
418 if(I[rvar].byte < I[ovar].byte)
419 boost::add_edge(rvar, ovar, I);
420 }
421
422 if(right && IS_SYMOP(right))
423 for(boost::tie(oio, oio_end) = n.operands.equal_range(OP_SYMBOL_CONST(right)->key); oio != oio_end; ++oio)
424 for(oirs = oir; oirs != oir_end; ++oirs)
425 {
426 var_t rvar = oirs->second;
427 var_t ovar = oio->second;
428 if(I[rvar].byte < I[ovar].byte)
429 boost::add_edge(rvar, ovar, I);
430 }
431 }
432
433 // Return true, iff the operand is placed (partially) in r.
434 template <class G_t>
operand_in_reg(const operand * o,reg_t r,const i_assignment_t & ia,unsigned short int i,const G_t & G)435 static bool operand_in_reg(const operand *o, reg_t r, const i_assignment_t &ia, unsigned short int i, const G_t &G)
436 {
437 if(!o || !IS_SYMOP(o))
438 return(false);
439
440 if(r >= port->num_regs)
441 return(false);
442
443 operand_map_t::const_iterator oi, oi_end;
444 for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
445 if(oi->second == ia.registers[r][1] || oi->second == ia.registers[r][0])
446 return(true);
447
448 return(false);
449 }
450
451 // Return true, iff the operand is placed in a reg.
452 template <class G_t>
operand_in_reg(const operand * o,const i_assignment_t & ia,unsigned short int i,const G_t & G)453 static bool operand_in_reg(const operand *o, const i_assignment_t &ia, unsigned short int i, const G_t &G)
454 {
455 if(!o || !IS_SYMOP(o))
456 return(false);
457
458 operand_map_t::const_iterator oi, oi_end;
459 for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
460 for(reg_t r = 0; r < port->num_regs; r++)
461 if(oi->second == ia.registers[r][1] || oi->second == ia.registers[r][0])
462 return(true);
463
464 return(false);
465 }
466
467 // Return true, iff the operand is placed in a reg.
468 template <class G_t>
operand_byte_in_reg(const operand * o,int offset,reg_t r,const assignment & a,unsigned short int i,const G_t & G)469 static bool operand_byte_in_reg(const operand *o, int offset, reg_t r, const assignment &a, unsigned short int i, const G_t &G)
470 {
471 if(!o || !IS_SYMOP(o))
472 return(false);
473
474 operand_map_t::const_iterator oi, oi2, oi3, oi_end;
475
476 for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); offset && oi != oi_end; offset--, oi++);
477
478 if(oi == oi_end)
479 return(false);
480
481 return(a.global[oi->second] == r);
482 }
483
484 // Return true, iff the operand is placed on the stack.
485 template <class G_t>
operand_on_stack(const operand * o,const assignment & a,unsigned short int i,const G_t & G)486 bool operand_on_stack(const operand *o, const assignment &a, unsigned short int i, const G_t &G)
487 {
488 if(!o || !IS_SYMOP(o))
489 return(false);
490
491 if(OP_SYMBOL_CONST(o)->remat)
492 return(false);
493
494 if(OP_SYMBOL_CONST(o)->_isparm && !IS_REGPARM (OP_SYMBOL_CONST(o)->etype))
495 return(true);
496
497 operand_map_t::const_iterator oi, oi_end;
498 for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
499 if(a.global[oi->second] < 0)
500 return(true);
501
502 return(false);
503 }
504
505 template <class G_t>
operand_is_pair(const operand * o,const assignment & a,unsigned short int i,const G_t & G)506 static bool operand_is_pair(const operand *o, const assignment &a, unsigned short int i, const G_t &G)
507 {
508 if(!o || !IS_SYMOP(o))
509 return(false);
510
511 operand_map_t::const_iterator oi, oi2, oi3, oi_end;
512 boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key);
513 if(oi == oi_end)
514 return(false);
515 oi2 = oi;
516 ++oi2;
517 if(oi2 == oi_end)
518 return(false);
519 oi3 = oi2;
520 ++oi3;
521 if(oi3 != oi_end)
522 return(false);
523
524 if(a.global[oi->second] != REG_C && a.global[oi->second] != REG_E && a.global[oi->second] != REG_L && a.global[oi->second] != REG_IYL)
525 return(false);
526 if(a.global[oi->second] + 1 != a.global[oi2->second])
527 return(false);
528
529 return(true);
530 }
531
532 template <class G_t, class I_t>
Ainst_ok(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)533 static bool Ainst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
534 {
535 const iCode *ic = G[i].ic;
536
537 const i_assignment_t &ia = a.i_assignment;
538
539 operand *const left = IC_LEFT(ic);
540 operand *const right = IC_RIGHT(ic);
541 const operand *const result = IC_RESULT(ic);
542
543 if(ia.registers[REG_A][1] < 0)
544 return(true); // Register A not in use.
545
546 // Some instructions don't touch registers.
547 if(SKIP_IC2(ic))
548 return(true);
549
550 bool exstk = (should_omit_frame_ptr || (currFunc && currFunc->stack > 127) || IS_GB);
551
552 //std::cout << "Ainst_ok at " << G[i].ic->key << ": A = (" << ia.registers[REG_A][0] << ", " << ia.registers[REG_A][1] << "), inst " << i << ", " << ic->key << "\n";
553
554 // Check if the result of this instruction is placed in A.
555 bool result_in_A = operand_in_reg(IC_RESULT(ic), REG_A, ia, i, G);
556
557 // Check if an input of this instruction is placed in A.
558 bool input_in_A;
559 switch(ic->op)
560 {
561 case IFX:
562 input_in_A = operand_in_reg(IC_COND(ic), REG_A, ia, i, G);
563 break;
564 case JUMPTABLE:
565 input_in_A = operand_in_reg(IC_JTCOND(ic), REG_A, ia, i, G);
566 break;
567 default:
568 input_in_A = operand_in_reg(left, REG_A, ia, i, G) || operand_in_reg(right, REG_A, ia, i, G);
569 break;
570 }
571
572 // sfr access needs to go through a.
573 if(input_in_A &&
574 (IS_TRUE_SYMOP (left) && IN_REGSP (SPEC_OCLS (OP_SYMBOL (left)->etype)) ||
575 IS_TRUE_SYMOP (right) && IN_REGSP (SPEC_OCLS (OP_SYMBOL (right)->etype))))
576 return(false);
577
578 if (ic->op == '^' || ic->op == BITWISEAND || ic->op == '|' || ic->op == '~') // Codegen can handle it all.
579 return(true);
580
581 if (ic->op == RIGHT_OP && getSize(operandType(result)) == 1 && IS_OP_LITERAL(right))
582 return(true);
583
584 // Can use non-destructive cp on == and < (> might swap operands).
585 if((ic->op == EQ_OP || ic->op == '<' && SPEC_USIGN(getSpec(operandType(left))) && SPEC_USIGN(getSpec(operandType(right)))) &&
586 getSize(operandType(IC_LEFT(ic))) == 1 && ifxForOp (IC_RESULT(ic), ic) && operand_in_reg(left, REG_A, ia, i, G) &&
587 (IS_OP_LITERAL (right) || operand_in_reg(right, REG_C, ia, i, G) || operand_in_reg(right, REG_B, ia, i, G) || operand_in_reg(right, REG_E, ia, i, G) || operand_in_reg(right, REG_D, ia, i, G) || operand_in_reg(right, REG_H, ia, i, G) || operand_in_reg(right, REG_L, ia, i, G)))
588 return(true);
589
590 const cfg_dying_t &dying = G[i].dying;
591 const bool dying_A = result_in_A || dying.find(ia.registers[REG_A][1]) != dying.end() || dying.find(ia.registers[REG_A][0]) != dying.end();
592
593 if((ic->op == '+' || ic->op == '-' && !operand_in_reg(right, REG_A, ia, i, G) || ic->op == UNARYMINUS && !IS_GB) &&
594 getSize(operandType(IC_RESULT(ic))) == 1 && dying_A)
595 return(true);
596
597 if((ic->op == '+' || ic->op == '-' && !operand_in_reg(right, REG_A, ia, i, G) || ic->op == UNARYMINUS && !IS_GB || ic->op == '~') && // First byte of input and last byte of output may be in A.
598 IS_ITEMP(result) && dying_A &&
599 (IS_ITEMP(left) || IS_OP_LITERAL(left) || operand_on_stack(left, a, i, G)) &&
600 (!right || IS_ITEMP(right) || IS_OP_LITERAL(right) || operand_on_stack(right, a, i, G)))
601 {
602
603 if((operand_byte_in_reg(left, 0, REG_A, a, i, G) || !operand_in_reg(left, REG_A, ia, i, G)) &&
604 (operand_byte_in_reg(right, 0, REG_A, a, i, G) || !operand_in_reg(right, REG_A, ia, i, G)) &&
605 (operand_byte_in_reg(result, getSize(operandType(IC_RESULT(ic))) - 1, REG_A, a, i, G) || !result_in_A))
606 return(true);
607 }
608
609 // First two bytes of input may be in A.
610 if(ic->op == IFX && dying_A && (getSize(operandType(left)) >= 1 &&
611 operand_byte_in_reg(left, 0, REG_A, a, i, G) || getSize(operandType(left)) >= 2 && !IS_FLOAT (operandType(left)) && operand_byte_in_reg(left, 1, REG_A, a, i, G)))
612 return(true);
613
614 // Plain assignment between registers
615 if(ic->op == CAST && getSize(operandType(IC_RESULT(ic))) == 1 &&
616 (operand_in_reg(result, REG_B, ia, i, G) || operand_in_reg(result, REG_C, ia, i, G) || operand_in_reg(result, REG_D, ia, i, G) || operand_in_reg(result, REG_E, ia, i, G) || operand_in_reg(result, REG_A, ia, i, G)) &&
617 (operand_in_reg(result, REG_B, ia, i, G) || operand_in_reg(result, REG_C, ia, i, G) || operand_in_reg(result, REG_D, ia, i, G) || operand_in_reg(result, REG_E, ia, i, G)))
618 return(true);
619
620 // Any input byte in A is ok, when all operands are registers other than iy.
621 if(ic->op == CAST && operand_in_reg(right, REG_A, ia, i, G) &&
622 !operand_in_reg(result, REG_A, ia, i, G) && (operand_in_reg(result, REG_C, ia, i, G) || operand_in_reg(result, REG_E, ia, i, G) || operand_in_reg(result, REG_L, ia, i, G)))
623 return(true);
624
625 // Last byte of output may be in A.
626 if((ic->op == GET_VALUE_AT_ADDRESS || ic->op == CAST && !operand_in_reg(right, REG_A, ia, i, G)) && IS_ITEMP(result) && operand_byte_in_reg(result, getSize(operandType(IC_RESULT(ic))) - 1, REG_A, a, i, G))
627 return(true);
628
629 if (ic->op == LEFT_OP && getSize(operandType(IC_RESULT(ic))) == 2 && IS_OP_LITERAL(right) && byteOfVal (OP_VALUE (IC_RIGHT(ic)), 0) == 7)
630 {
631 if(!operand_in_reg(left, REG_A, ia, i, G) || dying_A)
632 return(true);
633 }
634
635 // Left shift of 1 byte can always handle a.
636 if (ic->op == LEFT_OP && getSize(operandType(IC_RESULT(ic))) == 1 && IS_OP_LITERAL(right))
637 return(true);
638
639 // inc / dec does not affect a.
640 if ((ic->op == '+' || ic->op == '-') && IS_OP_LITERAL(right) && ulFromVal (OP_VALUE (IC_RIGHT(ic))) <= 2 &&
641 (getSize(operandType(IC_RESULT(ic))) == 2 && operand_is_pair(IC_RESULT(ic), a, i, G) || getSize(operandType(IC_RESULT(ic))) == 1 && operand_in_reg(result, ia, i, G) && operand_in_reg(result, ia, i, G)))
642 return(true);
643
644 if(ic->op == GET_VALUE_AT_ADDRESS) // Any register can be assigned from (hl) and (iy), so we don't need to go through a then.
645 return(!IS_BITVAR(getSpec(operandType(result))) &&
646 (getSize(operandType(result)) == 1 || operand_is_pair(left, a, i, G) && (operand_in_reg(left, REG_L, ia, i, G) && !ulFromVal (OP_VALUE (IC_RIGHT(ic))) || operand_in_reg(left, REG_IYL, ia, i, G) && ulFromVal (OP_VALUE (IC_RIGHT(ic))) <= 127)));
647
648 if(ic->op == '=' && POINTER_SET (ic) && // Any register can be assigned to (hl) and (iy), so we don't need to go through a then.
649 !(IS_BITVAR(getSpec(operandType (result))) || IS_BITVAR(getSpec(operandType (right)))) &&
650 (getSize(operandType(right)) == 1 || operand_is_pair(result, a, i, G) && (operand_in_reg(result, REG_L, ia, i, G) || operand_in_reg(result, REG_IYL, ia, i, G))))
651 return(true);
652
653 // Code generator mostly cannot handle variables that are only partially in A.
654 if(operand_in_reg(left, REG_A, ia, i, G) && getSize(operandType(left)) != 1 ||
655 operand_in_reg(right, REG_A, ia, i, G) && getSize(operandType(right)) != 1 ||
656 operand_in_reg(result, REG_A, ia, i, G) && getSize(operandType(result)) != 1)
657 return(false);
658
659 if(ic->op == '!' && getSize(operandType(left)) <= 2 && dying_A)
660 return(true);
661
662 if(ic->op == '=' && POINTER_SET (ic))
663 return(dying_A || !(IS_BITVAR(getSpec(operandType (result))) || IS_BITVAR(getSpec(operandType (right)))));
664
665 if(1)
666 {
667 // Variable in A is not used by this instruction
668 if(ic->op == '+' && IS_ITEMP (left) && IS_ITEMP (IC_RESULT(ic)) && IS_OP_LITERAL (right) &&
669 ulFromVal (OP_VALUE (IC_RIGHT(ic))) == 1 &&
670 OP_KEY (IC_RESULT(ic)) == OP_KEY (IC_LEFT(ic)))
671 return(true);
672
673 if((ic->op == '=' || ic->op == CAST) && !POINTER_SET (ic) && isOperandEqual (result, right))
674 return(true);
675
676 if((ic->op == '=' || ic->op == CAST) && !POINTER_SET (ic) && !(ic->op == CAST && IS_BOOL (operandType (result))) &&
677 (operand_in_reg(right, REG_A, ia, i, G) || operand_in_reg(right, REG_B, ia, i, G) || operand_in_reg(right, REG_C, ia, i, G) || operand_in_reg(right, REG_D, ia, i, G) || operand_in_reg(right, REG_E, ia, i, G) || operand_in_reg(right, REG_H, ia, i, G) || operand_in_reg(right, REG_L, ia, i, G)) &&
678 (operand_in_reg(right, REG_A, ia, i, G) || operand_in_reg(result, REG_B, ia, i, G) || operand_in_reg(result, REG_C, ia, i, G) || operand_in_reg(result, REG_D, ia, i, G) || operand_in_reg(result, REG_E, ia, i, G) || operand_in_reg(right, REG_H, ia, i, G) || operand_in_reg(right, REG_L, ia, i, G)))
679 return(true);
680
681 if(ic->op == GOTO || ic->op == LABEL)
682 return(true);
683
684 if(ic->op == IPUSH && getSize(operandType(IC_LEFT(ic))) <= 2 &&
685 (operand_in_reg(left, REG_A, ia, i, G) ||
686 operand_in_reg(left, REG_B, ia, i, G) && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_C, ia, i, G) && I[ia.registers[REG_C][1]].byte == 0) ||
687 operand_in_reg(left, REG_D, ia, i, G) && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_E, ia, i, G) && I[ia.registers[REG_E][1]].byte == 0) ||
688 operand_in_reg(left, REG_H, ia, i, G) && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_L, ia, i, G) && I[ia.registers[REG_L][1]].byte == 0) ||
689 operand_in_reg(left, REG_IYL, ia, i, G) && I[ia.registers[REG_IYL][1]].byte == 0 && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_IYH, ia, i, G))))
690 return(true);
691 if(!result_in_A && !input_in_A)
692 return(false);
693 }
694
695 // Last use of operand in A.
696 if(input_in_A && dying_A)
697 {
698 if(ic->op != IFX &&
699 ic->op != RETURN &&
700 !((ic->op == RIGHT_OP || ic->op == LEFT_OP) &&
701 (IS_OP_LITERAL(right) || operand_in_reg(right, REG_A, ia, i, G) || getSize(operandType(IC_RESULT(ic))) == 1 && ia.registers[REG_B][1] < 0)) &&
702 !((ic->op == '=' || ic->op == CAST) && !(IY_RESERVED && POINTER_SET(ic))) &&
703 !IS_BITWISE_OP (ic) &&
704 !(ic->op == '~') &&
705 !(ic->op == '*' && (IS_ITEMP(IC_LEFT(ic)) || IS_OP_LITERAL(IC_LEFT(ic))) && (IS_ITEMP(IC_RIGHT(ic)) || IS_OP_LITERAL(IC_RIGHT(ic)))) &&
706 !((ic->op == '-' || ic->op == '+' || ic->op == EQ_OP) && IS_OP_LITERAL(IC_RIGHT(ic))))
707 {
708 //std::cout << "Last use: Dropping at " << i << ", " << ic->key << "(" << int(ic->op) << ")\n";
709 return(false);
710 }
711 }
712 // A is used, and has to be preserved for later use.
713 else if(input_in_A &&
714 ic->op != IFX &&
715 ic->op != JUMPTABLE)
716 {
717 //std::cout << "Intermediate use: Dropping at " << i << ", " << ic->key << "(" << int(ic->op) << "\n";
718 return(false);
719 }
720
721 // First use of operand in A.
722 if(result_in_A &&
723 !POINTER_GET(ic) &&
724 ic->op != '+' &&
725 ic->op != '-' &&
726 (ic->op != '*' || !IS_OP_LITERAL(IC_LEFT(ic)) && !IS_OP_LITERAL(right)) &&
727 !IS_BITWISE_OP(ic) &&
728 ic->op != GET_VALUE_AT_ADDRESS &&
729 ic->op != '=' &&
730 ic->op != EQ_OP &&
731 ic->op != '<' &&
732 ic->op != '>' &&
733 ic->op != CAST &&
734 ic->op != CALL &&
735 ic->op != PCALL &&
736 ic->op != GETHBIT &&
737 !((ic->op == LEFT_OP || ic->op == RIGHT_OP) && IS_OP_LITERAL(right)))
738 {
739 //std::cout << "First use: Dropping at " << i << ", " << ic->key << "(" << int(ic->op) << "\n";
740 return(false);
741 }
742
743 //std::cout << "Default OK\n";
744
745 return(true);
746 }
747
748 template <class G_t, class I_t>
HLinst_ok(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)749 static bool HLinst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
750 {
751 const iCode *ic = G[i].ic;
752
753 // HL always unused on gbz80.
754 if(TARGET_IS_GBZ80)
755 return(true);
756
757 bool exstk = (should_omit_frame_ptr || (currFunc && currFunc->stack > 127) || IS_GB);
758
759 const i_assignment_t &ia = a.i_assignment;
760
761 bool unused_L = (ia.registers[REG_L][1] < 0);
762 bool unused_H = (ia.registers[REG_H][1] < 0);
763
764 if(unused_L && unused_H)
765 return(true); // Register HL not in use.
766
767 #if 0
768 if (ic->key == 3)
769 std::cout << "HLinst_ok: at (" << i << ", " << ic->key << ")\nL = (" << ia.registers[REG_L][0] << ", " << ia.registers[REG_L][1] << "), H = (" << ia.registers[REG_H][0] << ", " << ia.registers[REG_H][1] << ")inst " << i << ", " << ic->key << "\n";
770 #endif
771
772 const operand *left = IC_LEFT(ic);
773 const operand *right = IC_RIGHT(ic);
774 const operand *result = IC_RESULT(ic);
775
776 bool result_in_L = operand_in_reg(result, REG_L, ia, i, G);
777 bool result_in_H = operand_in_reg(result, REG_H, ia, i, G);
778 bool result_in_HL = result_in_L || result_in_H;
779
780 bool input_in_L, input_in_H;
781 switch(ic->op)
782 {
783 case IFX:
784 input_in_L = operand_in_reg(IC_COND(ic), REG_L, ia, i, G);
785 input_in_H = operand_in_reg(IC_COND(ic), REG_L, ia, i, G);
786 break;
787 case JUMPTABLE:
788 input_in_L = operand_in_reg(IC_JTCOND(ic), REG_L, ia, i, G);
789 input_in_H = operand_in_reg(IC_JTCOND(ic), REG_L, ia, i, G);
790 break;
791 default:
792 input_in_L = operand_in_reg(left, REG_L, ia, i, G) || operand_in_reg(right, REG_L, ia, i, G);
793 input_in_H = operand_in_reg(left, REG_H, ia, i, G) || operand_in_reg(right, REG_H, ia, i, G);
794 break;
795 }
796 bool input_in_HL = input_in_L || input_in_H;
797
798 const cfg_dying_t &dying = G[i].dying;
799
800 bool dying_L = result_in_L || dying.find(ia.registers[REG_L][1]) != dying.end() || dying.find(ia.registers[REG_L][0]) != dying.end();
801 bool dying_H = result_in_H || dying.find(ia.registers[REG_H][1]) != dying.end() || dying.find(ia.registers[REG_H][0]) != dying.end();
802
803 bool result_only_HL = (result_in_L || unused_L || dying_L) && (result_in_H || unused_H || dying_H);
804
805 #if 0
806 if (ic->key == 4)
807 {
808 std::cout << "Result in L: " << result_in_L << ", result in H: " << result_in_H << "\n";
809 std::cout << "Unsued L: " << unused_L << ", unused H: " << unused_H << "\n";
810 std::cout << "Dying L: " << dying_L << ", dying H: " << dying_H << "\n";
811 std::cout << "Result only HL: " << result_only_HL << "\n";
812 }
813 #endif
814
815 if(ic->op == RETURN || ic->op == SEND || ic->op == RECEIVE)
816 return(true);
817
818 if((IS_GB || IY_RESERVED) && (IS_TRUE_SYMOP(left) || IS_TRUE_SYMOP(right)))
819 return(false);
820
821 if((IS_GB || IY_RESERVED) && IS_TRUE_SYMOP(result) && getSize(operandType(IC_RESULT(ic))) > 2)
822 return(false);
823
824 // __z88dk_fastcall passes paramter in hl
825 if(ic->op == PCALL && ic->prev && ic->prev->op == SEND && input_in_HL && IFFUNC_ISZ88DK_FASTCALL(operandType(IC_LEFT(ic))->next))
826 return(false);
827
828 // HL overwritten by result.
829 if(result_only_HL && ic->op == PCALL)
830 return(true);
831
832 if(ic->op == '-' && getSize(operandType(result)) == 2 && !IS_GB && IS_TRUE_SYMOP (left) && IS_TRUE_SYMOP (right) && result_only_HL)
833 return(true);
834
835 if(exstk &&
836 (operand_on_stack(result, a, i, G) + operand_on_stack(left, a, i, G) + operand_on_stack(right, a, i, G) >= 2) &&
837 (result && IS_SYMOP(result) && getSize(operandType(result)) >= 2 || !result_only_HL))
838 // Todo: Make this more accurate to get better code when using --fomit-frame-pointer
839 return(false);
840 if(exstk && (operand_on_stack(left, a, i, G) || operand_on_stack(right, a, i, G)) && (ic->op == '>' || ic->op == '<'))
841 return(false);
842 if(ic->op == '+' && getSize(operandType(result)) >= 2 && input_in_HL &&
843 ((exstk ? operand_on_stack(left, a, i, G) : IS_TRUE_SYMOP (left) ) && (ia.registers[REG_L][1] > 0 || ia.registers[REG_H][1] > 0) ||
844 (exstk ? operand_on_stack(right, a, i, G) : IS_TRUE_SYMOP (right)) && (ia.registers[REG_L][1] > 0 || ia.registers[REG_H][1] > 0) ))
845 return(false);
846
847 if(ic->op == '+' && getSize(operandType(result)) == 2 &&
848 (IS_OP_LITERAL (right) && ulFromVal (OP_VALUE (IC_RIGHT(ic))) <= 3 || IS_OP_LITERAL (left) && ulFromVal (OP_VALUE (IC_LEFT(ic))) <= 3) &&
849 (operand_in_reg(result, REG_L, ia, i, G) && I[ia.registers[REG_L][1]].byte == 0 && operand_in_reg(result, REG_H, ia, i, G)))
850 return(true); // Uses inc hl.
851
852 if(ic->op == '+' && getSize(operandType(result)) == 2 && !IS_TRUE_SYMOP (result) &&
853 (result_only_HL || operand_in_reg(result, REG_IYL, ia, i, G) && operand_in_reg(result, REG_IYH, ia, i, G)) &&
854 (ia.registers[REG_C][1] < 0 && ia.registers[REG_B][1] < 0 || ia.registers[REG_E][1] < 0 && ia.registers[REG_D][1] < 0)) // Can use ld rr, (nn) instead of (hl).
855 return(true);
856
857 if(ic->op == '+' && getSize(operandType(result)) == 2 && IS_TRUE_SYMOP (left) && !IS_GB &&
858 (IS_OP_LITERAL (right) && ulFromVal (OP_VALUE (IC_RIGHT(ic))) <= 3 || IS_OP_LITERAL (left) && ulFromVal (OP_VALUE (IC_LEFT(ic))) <= 3) &&
859 (operand_in_reg(result, REG_C, ia, i, G) && I[ia.registers[REG_C][1]].byte == 0 && operand_in_reg(result, REG_B, ia, i, G) || operand_in_reg(result, REG_E, ia, i, G) && I[ia.registers[REG_E][1]].byte == 0 && operand_in_reg(result, REG_D, ia, i, G))) // Can use ld rr, (nn) followed by inc rr
860 return(true);
861
862 if((ic->op == '+' || ic->op == '-' || ic->op == UNARYMINUS) && getSize(operandType(result)) >= 2 &&
863 (IS_TRUE_SYMOP (result) && !operand_on_stack(result, a, i, G) || (operand_on_stack(left, a, i, G) ? exstk : IS_TRUE_SYMOP (left)) || (operand_on_stack(right, a, i, G) ? exstk : IS_TRUE_SYMOP (right)))) // Might use (hl).
864 return(false);
865
866 if(ic->op == '+' && input_in_HL && (operand_on_stack(result, a, i, G) ? exstk : IS_TRUE_SYMOP (result))) // Might use (hl) for result.
867 return(false);
868
869 // HL overwritten by result.
870 if(result_only_HL && !POINTER_SET(ic) &&
871 (ic->op == ADDRESS_OF ||
872 ic->op == GET_VALUE_AT_ADDRESS ||
873 ic->op == '+' ||
874 ic->op == '*' ||
875 ic->op == '=' ||
876 ic->op == CAST))
877 return(true);
878
879 if(!exstk && !isOperandInDirSpace(IC_LEFT(ic)) && !isOperandInDirSpace(IC_RIGHT(ic)) && !isOperandInDirSpace(IC_RESULT(ic)) &&
880 (ic->op == '-' ||
881 ic->op == UNARYMINUS ||
882 ic->op == '~' ||
883 ic->op == '<' ||
884 ic->op == '>'))
885 return(true);
886
887 if(ic->op == LEFT_OP && getSize(operandType(result)) <= 2 && IS_OP_LITERAL (right) && result_only_HL)
888 return(true);
889 if((ic->op == LEFT_OP || ic->op == RIGHT_OP) && (getSize(operandType(result)) <= 1 || !IS_TRUE_SYMOP(result) || !IY_RESERVED) &&
890 (!exstk ||
891 ((!operand_on_stack(left, a, i, G) || !input_in_HL && result_only_HL) &&
892 (!operand_on_stack(right, a, i, G) || !input_in_HL && result_only_HL) &&
893 !operand_on_stack(result, a, i, G))))
894 return(true);
895
896 if(result && IS_SYMOP(result) && isOperandInDirSpace(IC_RESULT(ic)))
897 return(false);
898
899 if((input_in_HL || !result_only_HL) && left && IS_SYMOP(left) && isOperandInDirSpace(IC_LEFT(ic)))
900 return(false);
901
902 if((input_in_HL || !result_only_HL) && right && IS_SYMOP(right) && isOperandInDirSpace(IC_RIGHT(ic)))
903 return(false);
904
905 // Operations that leave HL alone.
906 if(ic->op == IFX)
907 return(true);
908 if(SKIP_IC2(ic))
909 return(true);
910 if(ic->op == IPUSH && input_in_H && (getSize(operandType(IC_LEFT(ic))) <= 2 || ia.registers[REG_L][1] > 0 && I[ia.registers[REG_L][1]].byte == 2 && ia.registers[REG_H][1] > 0 && I[ia.registers[REG_H][1]].byte == 3))
911 return(true);
912 if(ic->op == IPUSH && getSize(operandType(left)) == 1 && IS_OP_LITERAL(left) && ia.registers[REG_A][1] < 0) // Can be pushed in A.
913 return(true);
914 if(ic->op == IPUSH && ic->next && ic->next->op == CALL)
915 return(true);
916 if(ic->op == IPUSH && getSize(operandType(left)) == 2 &&
917 (ia.registers[REG_C][1] < 0 && ia.registers[REG_B][1] < 0 || ia.registers[REG_E][1] < 0 && ia.registers[REG_D][1] < 0)) // Can use pair other than HL.
918 return(true);
919 if(ic->op == IPUSH && getSize(operandType(left)) <= 2 &&
920 (operand_in_reg(left, REG_C, ia, i, G) && I[ia.registers[REG_C][1]].byte == 0 && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_B, ia, i, G)) ||
921 operand_in_reg(left, REG_E, ia, i, G) && I[ia.registers[REG_E][1]].byte == 0 && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_D, ia, i, G)) ||
922 operand_in_reg(left, REG_IYL, ia, i, G) && I[ia.registers[REG_IYL][1]].byte == 0 && (getSize(operandType(left)) < 2 || operand_in_reg(left, REG_IYH, ia, i, G))))
923 return(true);
924 if (ic->op == IPUSH && getSize(operandType(left)) == 4 &&
925 operand_in_reg(left, REG_L, ia, i, G) && I[ia.registers[REG_L][1]].byte == 0 && operand_in_reg(left, REG_H, ia, i, G) && I[ia.registers[REG_H][1]].byte == 1 &&
926 (operand_in_reg(left, REG_C, ia, i, G) && I[ia.registers[REG_C][1]].byte == 2 && operand_in_reg(left, REG_B, ia, i, G) && I[ia.registers[REG_B][1]].byte == 3 ||
927 operand_in_reg(left, REG_E, ia, i, G) && I[ia.registers[REG_E][1]].byte == 2 && operand_in_reg(left, REG_D, ia, i, G) && I[ia.registers[REG_D][1]].byte == 3))
928 return(true);
929 if(POINTER_GET(ic) && input_in_L && input_in_H && (getSize(operandType(IC_RESULT(ic))) == 1 || !result_in_HL))
930 return(true);
931 if(!IS_GB && ic->op == ADDRESS_OF &&
932 (operand_in_reg(result, REG_IYL, ia, i, G) && ia.registers[REG_IYL][1] > 0 && I[ia.registers[REG_IYL][1]].byte == 0 && operand_in_reg(result, REG_IYH, ia, i, G) ||
933 !OP_SYMBOL_CONST (left)->onStack && operand_in_reg(result, REG_C, ia, i, G) && ia.registers[REG_C][1] > 0 && I[ia.registers[REG_C][1]].byte == 0 && operand_in_reg(result, REG_B, ia, i, G) ||
934 !OP_SYMBOL_CONST (left)->onStack && operand_in_reg(result, REG_E, ia, i, G) && ia.registers[REG_E][1] > 0 && I[ia.registers[REG_E][1]].byte == 0 && operand_in_reg(result, REG_D, ia, i, G)))
935 return(true);
936
937 if(ic->op == LEFT_OP && isOperandLiteral(IC_RIGHT(ic)))
938 return(true);
939
940 if(exstk && !result_only_HL && (operand_on_stack(left, a, i, G) || operand_on_stack(right, a, i, G) || operand_on_stack(result, a, i, G)) && ic->op == '+')
941 return(false);
942
943 if((!POINTER_SET(ic) && !POINTER_GET(ic) && (
944 (ic->op == '=' ||
945 ic->op == CAST ||
946 ic->op == UNARYMINUS ||
947 ic->op == RIGHT_OP ||
948 /*ic->op == '-' ||*/
949 IS_BITWISE_OP(ic) ||
950 /*ic->op == '>' ||
951 ic->op == '<' ||
952 ic->op == EQ_OP ||*/
953 (ic->op == '+' && getSize(operandType(IC_RESULT(ic))) == 1) ||
954 (ic->op == '+' && getSize(operandType(IC_RESULT(ic))) <= 2 && (result_only_HL || !IS_GB)) )))) // 16 bit addition on gbz80 might need to use add hl, rr.
955 return(true);
956
957 if((ic->op == '<' || ic->op == '>') && (IS_ITEMP(left) || IS_OP_LITERAL(left) || IS_ITEMP(right) || IS_OP_LITERAL(right))) // Todo: Fix for large stack.
958 return(true);
959
960 if(ic->op == EQ_OP && IS_VALOP(right))
961 return(true);
962
963 if(ic->op == CALL)
964 return(true);
965
966 if(POINTER_GET(ic) && getSize(operandType(IC_RESULT(ic))) == 1 && !IS_BITVAR(getSpec(operandType(result))) &&
967 (operand_in_reg(right, REG_C, ia, i, G) && I[ia.registers[REG_C][1]].byte == 0 && operand_in_reg(right, REG_B, ia, i, G) || // Uses ld a, (bc)
968 operand_in_reg(right, REG_E, ia, i, G) && I[ia.registers[REG_E][1]].byte == 0 && operand_in_reg(right, REG_D, ia, i, G) || // Uses ld a, (de)
969 operand_in_reg(right, REG_IYL, ia, i, G) && I[ia.registers[REG_IYL][1]].byte == 0 && operand_in_reg(right, REG_IYH, ia, i, G))) // Uses ld r, 0 (iy)
970 return(true);
971
972 if((ic->op == '=') && POINTER_SET(ic) && operand_in_reg(result, REG_IYL, ia, i, G) && I[ia.registers[REG_IYL][1]].byte == 0 && operand_in_reg(result, REG_IYH, ia, i, G)) // Uses ld 0 (iy), l etc
973 return(true);
974
975 if((ic->op == '=' || ic->op == CAST) && POINTER_SET(ic) && !result_only_HL) // loads result pointer into (hl) first.
976 return(false);
977
978 if((ic->op == '=' || ic->op == CAST) && !POINTER_GET(ic) && !input_in_HL)
979 return(true);
980
981 #if 0
982 if(ic->key == 4)
983 {
984 std::cout << "HLinst_ok: L = (" << ia.registers[REG_L][0] << ", " << ia.registers[REG_L][1] << "), H = (" << ia.registers[REG_H][0] << ", " << ia.registers[REG_H][1] << ")inst " << i << ", " << ic->key << "\n";
985 std::cout << "Result in L: " << result_in_L << ", result in H: " << result_in_H << "\n";
986 std::cout << "HL default drop at " << ic->key << ", operation: " << ic->op << "\n";
987 }
988 #endif
989
990 return(false);
991 }
992
993 template <class G_t, class I_t>
IYinst_ok(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)994 static bool IYinst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
995 {
996 const iCode *ic = G[i].ic;
997
998 // IY always unused on gbz80.
999 if(TARGET_IS_GBZ80)
1000 return(true);
1001
1002 const i_assignment_t &ia = a.i_assignment;
1003
1004 /*if(ic->key == 40)
1005 std::cout << "1IYinst_ok: at (" << i << ", " << ic->key << ")\nIYL = (" << ia.registers[REG_IYL][0] << ", " << ia.registers[REG_IYL][1] << "), IYH = (" << ia.registers[REG_IYH][0] << ", " << ia.registers[REG_IYH][1] << ")inst " << i << ", " << ic->key << "\n";*/
1006
1007 bool exstk = (should_omit_frame_ptr || (currFunc && currFunc->stack > 127));
1008
1009 bool unused_IYL = (ia.registers[REG_IYL][1] < 0);
1010 bool unused_IYH = (ia.registers[REG_IYH][1] < 0);
1011
1012 const operand *left = IC_LEFT(ic);
1013 const operand *right = IC_RIGHT(ic);
1014 const operand *result = IC_RESULT(ic);
1015
1016 bool result_in_IYL = operand_in_reg(result, REG_IYL, ia, i, G);
1017 bool result_in_IYH = operand_in_reg(result, REG_IYH, ia, i, G);
1018 bool result_in_IY = result_in_IYL || result_in_IYH;
1019
1020 bool input_in_IYL, input_in_IYH;
1021 switch(ic->op)
1022 {
1023 case IFX:
1024 input_in_IYL = operand_in_reg(IC_COND(ic), REG_IYL, ia, i, G);
1025 input_in_IYH = operand_in_reg(IC_COND(ic), REG_IYL, ia, i, G);
1026 break;
1027 case JUMPTABLE:
1028 input_in_IYL = operand_in_reg(IC_JTCOND(ic), REG_IYL, ia, i, G);
1029 input_in_IYH = operand_in_reg(IC_JTCOND(ic), REG_IYL, ia, i, G);
1030 break;
1031 default:
1032 input_in_IYL = operand_in_reg(left, REG_IYL, ia, i, G) || operand_in_reg(right, REG_IYL, ia, i, G);
1033 input_in_IYH = operand_in_reg(left, REG_IYH, ia, i, G) || operand_in_reg(right, REG_IYH, ia, i, G);
1034 break;
1035 }
1036 bool input_in_IY = input_in_IYL || input_in_IYH;
1037
1038 //const std::set<var_t> &dying = G[i].dying;
1039
1040 //bool dying_IYL = result_in_IYL || dying.find(ia.registers[REG_IYL][1]) != dying.end() || dying.find(ia.registers[REG_IYL][0]) != dying.end();
1041 //bool dying_IYH = result_in_IYH || dying.find(ia.registers[REG_IYH][1]) != dying.end() || dying.find(ia.registers[REG_IYH][0]) != dying.end();
1042
1043 //bool result_only_IY = (result_in_IYL || unused_IYL || dying_IYL) && (result_in_IYH || unused_IYH || dying_IYH);
1044
1045 if(unused_IYL && unused_IYH)
1046 return(true); // Register IY not in use.
1047
1048 if(SKIP_IC2(ic))
1049 return(true);
1050
1051 if(exstk && (operand_on_stack(result, a, i, G) || operand_on_stack(left, a, i, G) || operand_on_stack(right, a, i, G))) // Todo: Make this more accurate to get better code when using --fomit-frame-pointer
1052 return(false);
1053
1054 if(ic->op == CALL)
1055 return(true);
1056
1057 if(!result_in_IY && !input_in_IY &&
1058 !(IC_RESULT(ic) && isOperandInDirSpace(IC_RESULT(ic))) &&
1059 !(IC_RIGHT(ic) && IS_TRUE_SYMOP(IC_RIGHT(ic))) &&
1060 !(IC_LEFT(ic) && IS_TRUE_SYMOP(IC_LEFT(ic))))
1061 return(true);
1062
1063 // variables partially in IY can be pushed.
1064 if(ic->op == IPUSH &&
1065 operand_in_reg(left, REG_IYL, ia, i, G) && operand_in_reg(left, REG_IYH, ia, i, G) &&
1066 (I[ia.registers[REG_IYL][1]].byte == 0 && I[ia.registers[REG_IYH][1]].byte == 1 || I[ia.registers[REG_IYL][1]].byte == 2 && I[ia.registers[REG_IYH][1]].byte == 3))
1067 return(true);
1068
1069 // Code generator mostly cannot handle variables that are only partially in IY.
1070 if(unused_IYL ^ unused_IYH)
1071 return(false);
1072 if(!unused_IYL && I[ia.registers[REG_IYL][1]].size != 2 || !unused_IYH && I[ia.registers[REG_IYH][1]].size != 2 ||
1073 ia.registers[REG_IYL][0] >= 0 && I[ia.registers[REG_IYL][0]].size != 2 || ia.registers[REG_IYH][0] >= 0 && I[ia.registers[REG_IYH][0]].size != 2)
1074 return(false);
1075 if(ia.registers[REG_IYL][1] >= 0 && (ia.registers[REG_IYH][1] <= 0 || I[ia.registers[REG_IYL][1]].v != I[ia.registers[REG_IYH][1]].v))
1076 return(false);
1077 if(ia.registers[REG_IYH][1] >= 0 && (ia.registers[REG_IYL][1] <= 0 || I[ia.registers[REG_IYH][1]].v != I[ia.registers[REG_IYL][1]].v))
1078 return(false);
1079 if(ia.registers[REG_IYL][0] >= 0 && (ia.registers[REG_IYH][0] <= 0 || I[ia.registers[REG_IYL][0]].v != I[ia.registers[REG_IYH][0]].v))
1080 return(false);
1081 if(ia.registers[REG_IYH][0] >= 0 && (ia.registers[REG_IYL][0] <= 0 || I[ia.registers[REG_IYH][0]].v != I[ia.registers[REG_IYL][0]].v))
1082 return(false);
1083 if(I[ia.registers[REG_IYL][1]].byte != 0 || I[ia.registers[REG_IYH][1]].byte != 1)
1084 return(false);
1085 if(ia.registers[REG_IYL][0] >= 0 && I[ia.registers[REG_IYL][0]].byte != 0 || ia.registers[REG_IYH][0] >= 0 && I[ia.registers[REG_IYH][0]].byte != 1)
1086 return(false);
1087
1088 #if 0
1089 if(ic->key == 32)
1090 {
1091 std::cout << "A IYinst_ok: Assignment: ";
1092 //print_assignment(a);
1093 std::cout << "\n";
1094 std::cout << "2IYinst_ok: at (" << i << ", " << ic->key << ")\nIYL = (" << ia.registers[REG_IYL][0] << ", " << ia.registers[REG_IYL][1] << "), IYH = (" << ia.registers[REG_IYH][0] << ", " << ia.registers[REG_IYH][1] << ")inst " << i << ", " << ic->key << "\n";
1095 }
1096 #endif
1097
1098 if(result_in_IY &&
1099 (ic->op == '=' && !(POINTER_SET(ic) && isOperandInDirSpace(IC_RIGHT(ic))) ||
1100 ic->op == CAST && getSize(operandType(IC_RESULT(ic))) <= getSize(operandType(IC_RIGHT(ic))) ||
1101 ic->op == '+')) // todo: More instructions that can write iy.
1102 return(true);
1103
1104 // Todo: Multiplication.
1105
1106 if(ic->op == LEFT_OP && result_in_IY && input_in_IY && IS_VALOP (IC_RIGHT (ic)) && operandLitValue (IC_RIGHT (ic)) < 8)
1107 return(true);
1108
1109 if(ic->op == '-' && result_in_IY && input_in_IY && IS_VALOP (IC_RIGHT (ic)) && operandLitValue (IC_RIGHT (ic)) < 4)
1110 return(true);
1111
1112 #if 0
1113 if(ic->key == 32)
1114 {
1115 std::cout << "B IYinst_ok: Assignment: ";
1116 //print_assignment(a);
1117 std::cout << "\n";
1118 std::cout << "2IYinst_ok: at (" << i << ", " << ic->key << ")\nIYL = (" << ia.registers[REG_IYL][0] << ", " << ia.registers[REG_IYL][1] << "), IYH = (" << ia.registers[REG_IYH][0] << ", " << ia.registers[REG_IYH][1] << ")inst " << i << ", " << ic->key << "\n";
1119 }
1120 #endif
1121
1122 if(!result_in_IY && !input_in_IY &&
1123 (ic->op == '=' || ic->op == CAST && getSize(operandType(IC_RIGHT (ic))) >= 2 && (getSize(operandType(IC_RESULT (ic))) <= getSize(operandType(IC_RIGHT (ic))) || !IS_SPEC(operandType(IC_RIGHT (ic))) || SPEC_USIGN(operandType(IC_RIGHT(ic))))) &&
1124 operand_is_pair(IC_RESULT(ic), a, i, G)) // DirSpace access won't use iy here.
1125 return(true);
1126
1127 if(ic->op == IPUSH) // todo: More instructions that can use IY.
1128 return(true);
1129
1130 if(ic->op == GET_VALUE_AT_ADDRESS && isOperandInDirSpace(IC_RESULT(ic)))
1131 return(false);
1132
1133 if(input_in_IY && !result_in_IY &&
1134 (ic->op == '=' && !POINTER_SET(ic) ||
1135 ic->op == CAST && getSize(operandType(IC_RESULT(ic))) <= getSize(operandType(IC_RIGHT(ic))) ||
1136 ic->op == GET_VALUE_AT_ADDRESS))
1137 return(true);
1138
1139 #if 0
1140 if(ic->key == 99)
1141 {
1142 std::cout << "Default drop.\n";
1143 std::cout << "result is pair: " << operand_is_pair(IC_RESULT(ic), a, i, G) << "\n";
1144 }
1145 #endif
1146
1147 return(false);
1148 }
1149
1150 template <class G_t, class I_t>
DEinst_ok(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)1151 bool DEinst_ok(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
1152 {
1153 if(!IS_GB) // Only gbz80 might need de for code generation.
1154 return(true);
1155
1156 const i_assignment_t &ia = a.i_assignment;
1157
1158 bool unused_E = (ia.registers[REG_E][1] < 0);
1159 bool unused_D = (ia.registers[REG_D][1] < 0);
1160
1161 if(unused_E && unused_D)
1162 return(true); // Register DE not in use.
1163
1164 const iCode *ic = G[i].ic;
1165 const operand *left = IC_LEFT(ic);
1166 const operand *right = IC_RIGHT(ic);
1167 const operand *result = IC_RESULT(ic);
1168
1169 //const std::set<var_t> &dying = G[i].dying;
1170
1171 if(ic->op == PCALL)
1172 return(false);
1173
1174 if(ic->op == GET_VALUE_AT_ADDRESS && (getSize(operandType(result)) >= 2 || !operand_is_pair(left, a, i, G)))
1175 return(false);
1176
1177 if (ic->op == '=' && POINTER_SET(ic) && !operand_is_pair(result, a, i, G))
1178 return(false);
1179
1180 if((ic->op == '=' || ic->op == CAST) && getSize(operandType(result)) >= 2 &&
1181 (operand_on_stack(right, a, i, G) || operand_in_reg(right, REG_L, ia, i, G) || operand_in_reg(right, REG_H, ia, i, G)) &&
1182 (operand_on_stack(result, a, i, G) || operand_in_reg(result, REG_L, ia, i, G) || operand_in_reg(result, REG_H, ia, i, G)))
1183 return(false);
1184
1185 if(ic->op == '+' && getSize(operandType(result)) >= 2)
1186 return(false);
1187
1188 if(ic->op == UNARYMINUS || ic->op == '-' || ic->op == '*')
1189 return(false);
1190
1191 if(ic->op == '>' || ic->op == '<')
1192 return(false);
1193
1194 return(true);
1195 }
1196
1197 template <class G_t, class I_t>
set_surviving_regs(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)1198 static void set_surviving_regs(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
1199 {
1200 iCode *ic = G[i].ic;
1201
1202 bitVectClear(ic->rMask);
1203 bitVectClear(ic->rSurv);
1204
1205 cfg_alive_t::const_iterator v, v_end;
1206 for (v = G[i].alive.begin(), v_end = G[i].alive.end(); v != v_end; ++v)
1207 {
1208 if(a.global[*v] < 0)
1209 continue;
1210 ic->rMask = bitVectSetBit(ic->rMask, a.global[*v]);
1211
1212 if(G[i].dying.find(*v) == G[i].dying.end())
1213 if(!((IC_RESULT(ic) && !POINTER_SET(ic)) && IS_SYMOP(IC_RESULT(ic)) && OP_SYMBOL_CONST(IC_RESULT(ic))->key == I[*v].v))
1214 ic->rSurv = bitVectSetBit(ic->rSurv, a.global[*v]);
1215 }
1216 }
1217
1218 template <class G_t, class I_t>
assign_operand_for_cost(operand * o,const assignment & a,unsigned short int i,const G_t & G,const I_t & I)1219 static void assign_operand_for_cost(operand *o, const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
1220 {
1221 if(!o || !IS_SYMOP(o))
1222 return;
1223 symbol *sym = OP_SYMBOL(o);
1224 operand_map_t::const_iterator oi, oi_end;
1225 for(boost::tie(oi, oi_end) = G[i].operands.equal_range(OP_SYMBOL_CONST(o)->key); oi != oi_end; ++oi)
1226 {
1227 var_t v = oi->second;
1228 if(a.global[v] >= 0)
1229 {
1230 sym->regs[I[v].byte] = regsZ80 + a.global[v];
1231 sym->accuse = 0;
1232 sym->isspilt = false;
1233 sym->nRegs = I[v].size;
1234 }
1235 else
1236 {
1237 sym->isspilt = true;
1238 sym->accuse = 0;
1239 sym->nRegs = I[v].size;
1240 sym->regs[I[v].byte] = 0;
1241 }
1242 }
1243 }
1244
1245 template <class G_t, class I_t>
assign_operands_for_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)1246 static void assign_operands_for_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
1247 {
1248 const iCode *ic = G[i].ic;
1249
1250 if(ic->op == IFX)
1251 assign_operand_for_cost(IC_COND(ic), a, i, G, I);
1252 else if(ic->op == JUMPTABLE)
1253 assign_operand_for_cost(IC_JTCOND(ic), a, i, G, I);
1254 else
1255 {
1256 assign_operand_for_cost(IC_LEFT(ic), a, i, G, I);
1257 assign_operand_for_cost(IC_RIGHT(ic), a, i, G, I);
1258 assign_operand_for_cost(IC_RESULT(ic), a, i, G, I);
1259 }
1260
1261 if(ic->op == SEND && ic->builtinSEND)
1262 assign_operands_for_cost(a, (unsigned short)*(adjacent_vertices(i, G).first), G, I);
1263 }
1264
1265 // Cost function.
1266 template <class G_t, class I_t>
instruction_cost(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)1267 static float instruction_cost(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
1268 {
1269 iCode *ic = G[i].ic;
1270 float c;
1271
1272 wassert (TARGET_Z80_LIKE);
1273
1274 if(!inst_sane(a, i, G, I))
1275 return(std::numeric_limits<float>::infinity());
1276
1277 if(ic->generated)
1278 return(0.0f);
1279
1280 if(!Ainst_ok(a, i, G, I))
1281 return(std::numeric_limits<float>::infinity());
1282
1283 if(OPTRALLOC_HL && !HLinst_ok(a, i, G, I))
1284 return(std::numeric_limits<float>::infinity());
1285
1286 if(!DEinst_ok(a, i, G, I))
1287 return(std::numeric_limits<float>::infinity());
1288
1289 if(OPTRALLOC_IY && !IYinst_ok(a, i, G, I))
1290 return(std::numeric_limits<float>::infinity());
1291
1292 switch(ic->op)
1293 {
1294 // Register assignment doesn't matter for these:
1295 case FUNCTION:
1296 case ENDFUNCTION:
1297 case LABEL:
1298 case GOTO:
1299 case INLINEASM:
1300 return(0.0f);
1301 // Exact cost:
1302 case '!':
1303 case '~':
1304 case UNARYMINUS:
1305 case '+':
1306 case '-':
1307 case '^':
1308 case '|':
1309 case BITWISEAND:
1310 case IPUSH:
1311 //case IPOP:
1312 case CALL:
1313 case PCALL:
1314 case RETURN:
1315 case '*':
1316 case '>':
1317 case '<':
1318 case EQ_OP:
1319 case AND_OP:
1320 case OR_OP:
1321 case GETHBIT:
1322 case LEFT_OP:
1323 case RIGHT_OP:
1324 case GET_VALUE_AT_ADDRESS:
1325 case '=':
1326 case IFX:
1327 case ADDRESS_OF:
1328 case JUMPTABLE:
1329 case CAST:
1330 case RECEIVE:
1331 case SEND:
1332 case DUMMY_READ_VOLATILE:
1333 case CRITICAL:
1334 case ENDCRITICAL:
1335 assign_operands_for_cost(a, i, G, I);
1336 set_surviving_regs(a, i, G, I);
1337 c = dryZ80iCode(ic);
1338 ic->generated = false;
1339 return(c);
1340 // Inexact cost:
1341 default:
1342 return(default_instruction_cost(a, i, G, I));
1343 }
1344 }
1345
1346 template <class I_t>
weird_byte_order(const assignment & a,const I_t & I)1347 float weird_byte_order(const assignment &a, const I_t &I)
1348 {
1349 float c = 0.0f;
1350
1351 varset_t::const_iterator vi, vi_end;
1352 for(vi = a.local.begin(), vi_end = a.local.end(); vi != vi_end; ++vi)
1353 if(a.global[*vi] > 0 && (a.global[*vi] - 1) % 2 != I[*vi].byte % 2)
1354 c += 8.0f;
1355
1356 return(c);
1357 }
1358
1359 // Check for gaps, i.e. higher bytes of a variable being assigned to regs, while lower byte are not.
1360 template <class I_t>
local_assignment_insane(const assignment & a,const I_t & I,var_t lastvar)1361 bool local_assignment_insane(const assignment &a, const I_t &I, var_t lastvar)
1362 {
1363 varset_t::const_iterator v, v_end, v_old;
1364
1365 for(v = a.local.begin(), v_end = a.local.end(); v != v_end;)
1366 {
1367 v_old = v;
1368 ++v;
1369 if(v == v_end)
1370 {
1371 if(*v_old != lastvar && I[*v_old].byte != I[*v_old].size - 1)
1372 return(true);
1373 break;
1374 }
1375 if(I[*v_old].v == I[*v].v)
1376 {
1377 if(I[*v_old].byte != I[*v].byte - 1)
1378 return(true);
1379 }
1380 else
1381 {
1382 if(*v_old != lastvar && I[*v_old].byte != I[*v_old].size - 1 || I[*v].byte)
1383 return(true);
1384 }
1385 }
1386
1387 return(false);
1388 }
1389
1390 // For early removal of assignments that cannot be extended to valid assignments.
1391 template <class G_t, class I_t>
assignment_hopeless(const assignment & a,unsigned short int i,const G_t & G,const I_t & I,const var_t lastvar)1392 static bool assignment_hopeless(const assignment &a, unsigned short int i, const G_t &G, const I_t &I, const var_t lastvar)
1393 {
1394 if(local_assignment_insane(a, I, lastvar))
1395 return(true);
1396
1397 const i_assignment_t &ia = a.i_assignment;
1398
1399 // Can only check for HLinst_ok() in some cases.
1400 if(OPTRALLOC_HL &&
1401 (ia.registers[REG_L][1] >= 0 && ia.registers[REG_H][1] >= 0) &&
1402 (ia.registers[REG_L][0] >= 0 && ia.registers[REG_H][0] >= 0) &&
1403 !HLinst_ok(a, i, G, I))
1404 return(true);
1405
1406 // Can only check for IYinst_ok() in some cases.
1407 if(OPTRALLOC_IY &&
1408 (ia.registers[REG_IYL][1] >= 0 || ia.registers[REG_IYH][1] >= 0) &&
1409 !IYinst_ok(a, i, G, I))
1410 return(true);
1411
1412 return(false);
1413 }
1414
1415 // Increase chance of finding good compatible assignments at join nodes.
1416 template <class T_t>
get_best_local_assignment_biased(assignment & a,typename boost::graph_traits<T_t>::vertex_descriptor t,const T_t & T)1417 static void get_best_local_assignment_biased(assignment &a, typename boost::graph_traits<T_t>::vertex_descriptor t, const T_t &T)
1418 {
1419 const assignment_list_t &alist = T[t].assignments;
1420
1421 assignment_list_t::const_iterator ai, ai_end, ai_best;
1422 for(ai = ai_best = alist.begin(), ai_end = alist.end(); ai != ai_end; ++ai)
1423 {
1424 if(ai->s < ai_best->s)
1425 {
1426 varset_t::const_iterator vi, vi_end;
1427 for(vi = ai->local.begin(), vi_end = ai->local.end(); vi != vi_end; ++vi)
1428 if(ai->global[*vi] == REG_A || OPTRALLOC_HL && (ai->global[*vi] == REG_H || ai->global[*vi] == REG_L) || OPTRALLOC_IY && (ai->global[*vi] == REG_IYH || ai->global[*vi] == REG_IYL))
1429 goto too_risky;
1430 ai_best = ai;
1431 }
1432 too_risky:
1433 ;
1434 }
1435
1436 a = *ai_best;
1437
1438 std::set<var_t>::const_iterator vi, vi_end;
1439 varset_t newlocal;
1440 std::set_union(T[t].alive.begin(), T[t].alive.end(), a.local.begin(), a.local.end(), std::inserter(newlocal, newlocal.end()));
1441 a.local = newlocal;
1442 }
1443
1444 template <class G_t, class I_t>
rough_cost_estimate(const assignment & a,unsigned short int i,const G_t & G,const I_t & I)1445 static float rough_cost_estimate(const assignment &a, unsigned short int i, const G_t &G, const I_t &I)
1446 {
1447 const i_assignment_t &ia = a.i_assignment;
1448 float c = 0.0f;
1449
1450 c += weird_byte_order(a, I);
1451
1452 if(OPTRALLOC_HL &&
1453 ia.registers[REG_L][1] >= 0 &&
1454 ia.registers[REG_H][1] >= 0 &&
1455 ((ia.registers[REG_L][0] >= 0) == (ia.registers[REG_H][0] >= 0)) &&
1456 !HLinst_ok(a, i, G, I))
1457 c += 8.0f;
1458
1459 if(ia.registers[REG_A][1] < 0)
1460 c += 0.03f;
1461
1462 if(OPTRALLOC_HL && ia.registers[REG_L][1] < 0)
1463 c += 0.02f;
1464
1465 // Using IY is rarely a good choice, so discard the IY-users first when in doubt.
1466 if(OPTRALLOC_IY)
1467 {
1468 varset_t::const_iterator vi, vi_end;
1469 for(vi = a.local.begin(), vi_end = a.local.end(); vi != vi_end; ++vi)
1470 if(a.global[*vi] == REG_IYL || a.global[*vi] == REG_IYH)
1471 c += 8.0f;
1472 }
1473
1474 // An artifical ordering of assignments.
1475 if(ia.registers[REG_E][1] < 0)
1476 c += 0.0001f;
1477 if(ia.registers[REG_D][1] < 0)
1478 c += 0.00001f;
1479
1480 if(a.marked)
1481 c -= 0.5f;
1482
1483 varset_t::const_iterator v, v_end;
1484 for(v = a.local.begin(), v_end = a.local.end(); v != v_end; ++v)
1485 {
1486 const symbol *const sym = (symbol *)(hTabItemWithKey(liveRanges, I[*v].v));
1487 if(a.global[*v] < 0 && IS_REGISTER(sym->type)) // When in doubt, try to honour register keyword.
1488 c += 32.0f;
1489 if((I[*v].byte % 2) && (a.global[*v] == REG_L || a.global[*v] == REG_E || a.global[*v] == REG_C || a.global[*v] == REG_IYL)) // Try not to reverse bytes.
1490 c += 8.0f;
1491 if(!(I[*v].byte % 2) && I[*v].size > 1 && (a.global[*v] == REG_H || a.global[*v] == REG_D || a.global[*v] == REG_B || a.global[*v] == REG_IYH)) // Try not to reverse bytes.
1492 c += 8.0f;
1493 if(I[*v].byte == 0 && I[*v].size > 1 || I[*v].byte == 2 && I[*v].size > 3)
1494 {
1495 if (a.global[*v] == REG_L && a.global[*v + 1] >= 0 && a.global[*v + 1] != REG_H)
1496 c += 16.0f;
1497 if (a.global[*v] == REG_E && a.global[*v + 1] >= 0 && a.global[*v + 1] != REG_D)
1498 c += 16.0f;
1499 if (a.global[*v] == REG_C && a.global[*v + 1] >= 0 && a.global[*v + 1] != REG_B)
1500 c += 16.0f;
1501 }
1502 else if(I[*v].byte == 1 || I[*v].byte == 3)
1503 {
1504 if (a.global[*v] == REG_H && a.global[*v - 1] >= 0 && a.global[*v - 1] != REG_L)
1505 c += 16.0f;
1506 if (a.global[*v] == REG_D && a.global[*v - 1] >= 0 && a.global[*v - 1] != REG_E)
1507 c += 16.0f;
1508 if (a.global[*v] == REG_B && a.global[*v - 1] >= 0 && a.global[*v - 1] != REG_C)
1509 c += 16.0f;
1510 }
1511 }
1512
1513 c -= a.local.size() * 0.2f;
1514
1515 return(c);
1516 }
1517
1518 // Code for another ic is generated when generating this one. Mark the other as generated.
extra_ic_generated(iCode * ic)1519 static void extra_ic_generated(iCode *ic)
1520 {
1521 if(ic->op == '>' || ic->op == '<' || ic->op == LE_OP || ic->op == GE_OP || ic->op == EQ_OP || ic->op == NE_OP ||
1522 (ic->op == '^' || ic->op == '|' || ic->op == BITWISEAND) && (IS_OP_LITERAL (IC_LEFT (ic)) || IS_OP_LITERAL (IC_RIGHT (ic))))
1523 {
1524 iCode *ifx;
1525 if (ifx = ifxForOp (IC_RESULT (ic), ic))
1526 {
1527 OP_SYMBOL (IC_RESULT (ic))->for_newralloc = false;
1528 OP_SYMBOL (IC_RESULT (ic))->regType = REG_CND;
1529 ifx->generated = true;
1530 }
1531 }
1532
1533 if(ic->op == SEND && ic->builtinSEND && (!ic->prev || ic->prev->op != SEND || !ic->prev->builtinSEND))
1534 {
1535 iCode *icn;
1536 for(icn = ic->next; icn->op != CALL; icn = icn->next)
1537 icn->generated = true;
1538 icn->generated = true;
1539 ic->generated = false;
1540 }
1541 }
1542
1543 template <class T_t, class G_t, class I_t, class SI_t>
tree_dec_ralloc(T_t & T,G_t & G,const I_t & I,SI_t & SI)1544 static bool tree_dec_ralloc(T_t &T, G_t &G, const I_t &I, SI_t &SI)
1545 {
1546 bool assignment_optimal;
1547
1548 con2_t I2(boost::num_vertices(I));
1549 for(unsigned int i = 0; i < boost::num_vertices(I); i++)
1550 {
1551 I2[i].v = I[i].v;
1552 I2[i].byte = I[i].byte;
1553 I2[i].size = I[i].size;
1554 I2[i].name = I[i].name;
1555 }
1556 typename boost::graph_traits<I_t>::edge_iterator e, e_end;
1557 for(boost::tie(e, e_end) = boost::edges(I); e != e_end; ++e)
1558 add_edge(boost::source(*e, I), boost::target(*e, I), I2);
1559
1560 assignment ac;
1561 assignment_optimal = true;
1562 tree_dec_ralloc_nodes(T, find_root(T), G, I2, ac, &assignment_optimal);
1563
1564 const assignment &winner = *(T[find_root(T)].assignments.begin());
1565
1566 #ifdef DEBUG_RALLOC_DEC
1567 std::cout << "Winner: ";
1568 for(unsigned int i = 0; i < boost::num_vertices(I); i++)
1569 {
1570 std::cout << "(" << i << ", " << int(winner.global[i]) << ") ";
1571 }
1572 std::cout << "\n";
1573 std::cout << "Cost: " << winner.s << "\n";
1574 std::cout.flush();
1575 #endif
1576
1577 // Todo: Make this an assertion
1578 if(winner.global.size() != boost::num_vertices(I))
1579 {
1580 std::cerr << "ERROR: No Assignments at root\n";
1581 exit(-1);
1582 }
1583
1584 for(unsigned int v = 0; v < boost::num_vertices(I); v++)
1585 {
1586 symbol *sym = (symbol *)(hTabItemWithKey(liveRanges, I[v].v));
1587 if(winner.global[v] >= 0)
1588 {
1589
1590 sym->regs[I[v].byte] = regsZ80 + winner.global[v];
1591 sym->accuse = 0;
1592 sym->isspilt = false;
1593 sym->nRegs = I[v].size;
1594 }
1595 else
1596 {
1597 for(int i = 0; i < I[v].size; i++)
1598 sym->regs[i] = 0;
1599 sym->accuse = 0;
1600 sym->nRegs = I[v].size;
1601 if (USE_OLDSALLOC)
1602 sym->isspilt = false; // Leave it to Z80RegFix, which can do some spillocation compaction.
1603 else
1604 z80SpillThis(sym);
1605 }
1606 }
1607
1608 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
1609 set_surviving_regs(winner, i, G, I);
1610
1611 if (!USE_OLDSALLOC)
1612 set_spilt(G, I, SI);
1613
1614 return(!assignment_optimal);
1615 }
1616
1617 // Omit the frame pointer for functions with low register pressure and few parameter accesses.
1618 template <class G_t>
omit_frame_ptr(const G_t & G)1619 static bool omit_frame_ptr(const G_t &G)
1620 {
1621 if(IS_GB || IY_RESERVED || z80_opts.noOmitFramePtr)
1622 return(false);
1623
1624 if(options.omitFramePtr)
1625 return(true);
1626
1627 signed char omitcost = -16;
1628 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
1629 {
1630 if((int)G[i].alive.size() > port->num_regs - 4)
1631 return(false);
1632
1633 const iCode *const ic = G[i].ic;
1634 const operand *o;
1635 o = IC_RESULT(ic);
1636 if(o && IS_SYMOP(o) && OP_SYMBOL_CONST(o)->_isparm && !IS_REGPARM (OP_SYMBOL_CONST(o)->etype))
1637 omitcost += 6;
1638 o = IC_LEFT(ic);
1639 if(o && IS_SYMOP(o) && OP_SYMBOL_CONST(o)->_isparm && !IS_REGPARM (OP_SYMBOL_CONST(o)->etype))
1640 omitcost += 6;
1641 o = IC_RIGHT(ic);
1642 if(o && IS_SYMOP(o) && OP_SYMBOL_CONST(o)->_isparm && !IS_REGPARM (OP_SYMBOL_CONST(o)->etype))
1643 omitcost += 6;
1644
1645 if(omitcost > 14) // Chosen greater than zero, since the peephole optimizer often can optimize the use of iy into use of hl, reducing the cost.
1646 return(false);
1647 }
1648
1649 return(true);
1650 }
1651
1652 // Adjust stack location when deciding to omit frame pointer.
move_parms(void)1653 void move_parms(void)
1654 {
1655 if(!currFunc || IS_GB || options.omitFramePtr || !should_omit_frame_ptr)
1656 return;
1657
1658 for(value *val = FUNC_ARGS (currFunc->type); val; val = val->next)
1659 {
1660 if(IS_REGPARM(val->sym->etype) || !val->sym->onStack)
1661 continue;
1662
1663 val->sym->stack -= 2;
1664 }
1665 }
1666
z80_ralloc2_cc(ebbIndex * ebbi)1667 iCode *z80_ralloc2_cc(ebbIndex *ebbi)
1668 {
1669 eBBlock **const ebbs = ebbi->bbOrder;
1670 const int count = ebbi->count;
1671
1672 #ifdef DEBUG_RALLOC_DEC
1673 std::cout << "Processing " << currFunc->name << " from " << dstFileName << "\n"; std::cout.flush();
1674 #endif
1675
1676 cfg_t control_flow_graph;
1677
1678 con_t conflict_graph;
1679
1680 iCode *ic = create_cfg(control_flow_graph, conflict_graph, ebbi);
1681
1682 should_omit_frame_ptr = omit_frame_ptr(control_flow_graph);
1683 move_parms();
1684
1685 if(options.dump_graphs)
1686 dump_cfg(control_flow_graph);
1687
1688 if(options.dump_graphs)
1689 dump_con(conflict_graph);
1690
1691 tree_dec_t tree_decomposition;
1692
1693 get_nice_tree_decomposition(tree_decomposition, control_flow_graph);
1694
1695 alive_tree_dec(tree_decomposition, control_flow_graph);
1696
1697 good_re_root(tree_decomposition);
1698 nicify(tree_decomposition);
1699 alive_tree_dec(tree_decomposition, control_flow_graph);
1700
1701 if(options.dump_graphs)
1702 dump_tree_decomposition(tree_decomposition);
1703
1704 guessCounts (ic, ebbi);
1705
1706 scon_t stack_conflict_graph;
1707
1708 z80_assignment_optimal = !tree_dec_ralloc(tree_decomposition, control_flow_graph, conflict_graph, stack_conflict_graph);
1709
1710 Z80RegFix (ebbs, count);
1711
1712 if (USE_OLDSALLOC)
1713 redoStackOffsets ();
1714 else
1715 chaitin_salloc(stack_conflict_graph); // new Chaitin-style stack allocator
1716
1717 if(options.dump_graphs && !USE_OLDSALLOC)
1718 dump_scon(stack_conflict_graph);
1719
1720 return(ic);
1721 }
1722
1723