1 // Philipp Klaus Krause, philipp@informatik.uni-frankfurt.de, pkk@spth.de, 2011-2018
2 //
3 // (c) 2011-2012 Goethe-Universität Frankfurt
4 // (c) 2018 Albert-Ludwigs-Universität Frankfurt
5 //
6 // This program is free software; you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option) any
9 // later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 //
20 // A Chaitin-style stack allocator.
21
22 #ifndef SDCCSALLOC_HH
23 #define SDCCSALLOC_HH 1
24
25 #include <boost/graph/adjacency_list.hpp>
26
27 #include <boost/icl/discrete_interval.hpp>
28 #include <boost/icl/interval_set.hpp>
29
30 extern "C"
31 {
32 #include "SDCCmem.h"
33 #include "SDCCglobl.h"
34 }
35
36 // #define DEBUG_SALLOC
37
38 struct scon_node_t
39 {
40 symbol *sym;
41 int color;
42 boost::icl::interval_set<int> free_stack;
43 std::set<boost::icl::discrete_interval<int> > alignment_conflicts;
44 };
45
46 struct scon_edge_t
47 {
48 bool alignment_conflict_only;
49 };
50
51 typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, scon_node_t, scon_edge_t> scon_t; // Conflict graph for on-stack variables
52
clash(const symbol * s1,const symbol * s2)53 static bool clash (const symbol *s1, const symbol *s2)
54 {
55 wassert(s1);
56 wassert(s2);
57
58 if(!s1->isspilt && !(IS_AGGREGATE(s1->type) || s1->allocreq && (s1->addrtaken || isVolatile(s1->type)))) // Spill location
59 {
60 for(const symbol *s = (const symbol *)setFirstItem (s1->usl.itmpStack); s; s = (const symbol *)setNextItem (s1->usl.itmpStack))
61 if(clash(s, s2))
62 return(true);
63 return(false);
64 }
65 if(!s2->isspilt && !(IS_AGGREGATE(s2->type) || s2->allocreq && (s2->addrtaken || isVolatile(s2->type)))) // Spill location
66 {
67 for(const symbol *s = (const symbol *)setFirstItem (s2->usl.itmpStack); s; s = (const symbol *)setNextItem (s2->usl.itmpStack))
68 if(clash(s1, s))
69 return(true);
70 return(false);
71 }
72
73 return(bitVectBitValue (s1->clashes, s2->key));
74 }
75
var_from_operand(const std::map<const symbol *,var_t> & symbol_to_sindex,const operand * const op)76 static var_t var_from_operand(const std::map<const symbol *, var_t>& symbol_to_sindex, const operand *const op)
77 {
78 if(!op || !IS_SYMOP(op))
79 return(-1);
80 std::map<const symbol *, var_t>::const_iterator si = symbol_to_sindex.find(OP_SYMBOL_CONST(op));
81 if (si == symbol_to_sindex.end())
82 return(-1);
83
84 return(si->second);
85 }
86
87 template<class G_t, class I_t, class SI_t>
set_spilt(G_t & G,const I_t & I,SI_t & scon)88 static void set_spilt(G_t &G, const I_t &I, SI_t &scon)
89 {
90 std::map<const symbol *, var_t> symbol_to_sindex;
91 std::map<int, var_t> iindex_to_sindex;
92 symbol *sym;
93 var_t j, j_mark;
94
95 // Add variables that need to be on the stack due to having had their address taken (or for a few other reasons, such as being too large or too many to behandled by the register allocator).
96 for(sym = static_cast<symbol *>(setFirstItem(istack->syms)), j = 0; sym; sym = static_cast<symbol *>(setNextItem(istack->syms)))
97 {
98 if(sym->_isparm)
99 continue;
100
101 // std::cout << "set_spilt() 1: Considering " << sym->name << "[" << sym->isspilt << ", " << IS_AGGREGATE(sym->type) << ", " << sym->allocreq << ", " << sym->addrtaken << "]\n";
102
103 if(/*!(IS_AGGREGATE(sym->type) || sym->allocreq && (sym->addrtaken || isVolatile(sym->type)))*/sym->for_newralloc)
104 continue;
105
106 if(!sym->isspilt && !(IS_AGGREGATE(sym->type) || sym->allocreq && (sym->addrtaken || isVolatile(sym->type)))) // Looks like a spill location - check if it is already covered by live ranges below.
107 {
108 bool covered = true;
109 for (const symbol *s = (const symbol *)setFirstItem (sym->usl.itmpStack); s; s = (const symbol *)setNextItem (sym->usl.itmpStack))
110 if (!s->for_newralloc)
111 {
112 #ifdef DEBUG_SALLOC
113 std::cout << "Adding " << sym->name << " for " << s->name << "(" << s << ") to be allocated to stack. (" << s->for_newralloc << ")\n";
114 std::cout.flush();
115 #endif
116 covered = false;
117 symbol_to_sindex[s] = j;
118 break;
119 }
120 if(covered)
121 continue;
122 }
123
124 boost::add_vertex(scon);
125 symbol_to_sindex[sym] = j;
126 scon[j].sym = sym;
127 scon[j].color = -1;
128 j++;
129 }
130 j_mark = j;
131
132 // Add edges due to scope (see C99 standard, verse 1233, which requires things to have different addresses, not allowing us to allocate them to the same location, even if we otherwise could).
133 for(unsigned int i = 0; i < boost::num_vertices(scon); i++)
134 for(unsigned int j = i + 1; j < boost::num_vertices(scon); j++)
135 {
136 if (!(scon[i].sym->addrtaken) || !(scon[i].sym->addrtaken))
137 continue;
138 short p = btree_lowest_common_ancestor(scon[i].sym->block, scon[j].sym->block);
139 if(p == scon[i].sym->block || p == scon[j].sym->block)
140 boost::add_edge(i, j, scon);
141 }
142
143 // Set stack live ranges
144 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
145 {
146 G[i].ic->localEscapeAlive = false;
147
148 for(unsigned int j = 0; j < boost::num_vertices(scon); j++)
149 {
150 short p = btree_lowest_common_ancestor(G[i].ic->block, scon[j].sym->block);
151 if(p == G[i].ic->block || p == scon[j].sym->block)
152 {
153 G[i].stack_alive.insert(j);
154 if (scon[j].sym->addrtaken || IS_AGGREGATE(scon[j].sym->type) ) // TODO: More accurate analysis.
155 G[i].ic->localEscapeAlive = true;
156 }
157 }
158 }
159
160 // Add variables that have been spilt in register allocation.
161 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
162 {
163 cfg_alive_t::const_iterator v, v_end;
164 for (v = G[i].alive.begin(), v_end = G[i].alive.end(); v != v_end; ++v)
165 {
166 var_t vs;
167
168 symbol *const sym = (symbol *)(hTabItemWithKey(liveRanges, I[*v].v));
169
170 if ((sym->regs[0] && !sym->isspilt) || sym->accuse || sym->remat || !sym->nRegs || sym->usl.spillLoc && sym->usl.spillLoc->_isparm)
171 continue;
172
173 if (iindex_to_sindex.find(I[*v].v) == iindex_to_sindex.end())
174 {
175 wassert(boost::add_vertex(scon) == j);
176 scon[j].sym = sym;
177 scon[j].color = -1;
178 iindex_to_sindex[I[*v].v] = j;
179 symbol_to_sindex[sym] = j;
180 j++;
181 }
182
183 vs = iindex_to_sindex[I[*v].v];
184
185 G[i].stack_alive.insert(vs); // Needs to be allocated on the stack.
186 }
187 }
188
189 // Add edges to conflict graph.
190 typename boost::graph_traits<I_t>::edge_iterator e, e_end;
191 for (boost::tie(e, e_end) = boost::edges(I); e != e_end; ++e)
192 {
193 if (I[boost::source(*e, I)].v == I[boost::target(*e, I)].v || iindex_to_sindex.find(I[boost::source(*e, I)].v) == iindex_to_sindex.end() || iindex_to_sindex.find(I[boost::target(*e, I)].v) == iindex_to_sindex.end())
194 continue;
195
196 boost::add_edge(iindex_to_sindex[I[boost::source(*e, I)].v], iindex_to_sindex[I[boost::target(*e, I)].v], scon);
197 }
198
199 // Add conflicts between variables that had their address taken and those that have been spilt by register allocation.
200 // TODO: More exact live range analysis for variables that had their address taken (to reduce stack space consumption further, by reducing the number of conflicts here).
201 for(unsigned int i = 0; i < j_mark; i++)
202 for(unsigned int j = 0; j < boost::num_vertices(scon); j++)
203 {
204 if (i == j)
205 continue;
206 if(!scon[i].sym->isspilt && !(IS_AGGREGATE(scon[i].sym->type) || scon[i].sym->allocreq && (scon[i].sym->addrtaken || isVolatile(scon[i].sym->type)))) // Spill location
207 {
208 if (clash (scon[i].sym, scon[j].sym))
209 boost::add_edge(i, j, scon);
210 continue;
211 }
212 short p = btree_lowest_common_ancestor(scon[i].sym->block, scon[j].sym->block);
213 if(p == scon[i].sym->block || p == scon[j].sym->block)
214 boost::add_edge(i, j, scon);
215 }
216
217 // Ugly hack: Regparms.
218 for(sym = static_cast<symbol *>(setFirstItem(istack->syms)), j = boost::num_vertices(scon); sym; sym = static_cast<symbol *>(setNextItem(istack->syms)))
219 {
220 if(!sym->_isparm || !IS_REGPARM(sym->etype) || !sym->onStack || !sym->allocreq)
221 continue;
222
223 boost::add_vertex(scon);
224 scon[j].sym = sym;
225 scon[j].color = -1;
226
227 // Extend liverange to cover everything.
228 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
229 G[i].stack_alive.insert(j);
230
231 // Conflict with everything.
232 for(unsigned int i = 0; i < j; i++)
233 boost::add_edge(i, j, scon);
234
235 j++;
236 }
237
238 // Edges for aligment conflict
239 typename SI_t::edge_iterator ei, ei_end;
240 for(boost::tie(ei, ei_end) = boost::edges(scon); ei != ei_end; ++ei)
241 scon[*ei].alignment_conflict_only = false;
242 for(unsigned int i = 0; i < boost::num_vertices(G); i++)
243 {
244 const var_t result = var_from_operand (symbol_to_sindex, IC_RESULT(G[i].ic));
245
246 if(result < 0)
247 continue;
248
249 const var_t left = var_from_operand (symbol_to_sindex, IC_LEFT(G[i].ic));
250 const var_t right = var_from_operand (symbol_to_sindex, IC_RIGHT(G[i].ic));
251
252 if(left >= 0 && !boost::edge (result, left, scon).second)
253 scon[(boost::add_edge(result, left, scon)).first].alignment_conflict_only =
254 !(TARGET_PDK_LIKE && G[i].ic->op == GET_VALUE_AT_ADDRESS && getSize(scon[result].sym->type) > 2); // Padauk still needs pointer read operand, since pointer read of more than 2 bytes is broken into multiple support routine calls.
255 if(right >= 0 && !boost::edge (result, right, scon).second)
256 scon[(boost::add_edge(result, right, scon)).first].alignment_conflict_only = true;
257 }
258 }
259
260 template <class SI_t>
color_stack_var(const var_t v,SI_t & SI,int start,int * ssize)261 void color_stack_var(const var_t v, SI_t &SI, int start, int *ssize)
262 {
263 symbol *const sym = SI[v].sym;
264 const int size = getSize(sym->type);
265
266 SI[v].color = start;
267
268 const int sloc = (port->stack.direction > 0) ? start : -start - size ;
269 symbol *const ssym = (sym->isspilt && sym->usl.spillLoc) ? sym->usl.spillLoc : sym;
270
271 SPEC_STAK(ssym->etype) = ssym->stack = sloc;
272
273 if(ssize)
274 *ssize = (start + size > *ssize) ? start + size : *ssize;
275
276 #ifdef DEBUG_SALLOC
277 std::cout << "Placing " << sym->name << " (really " << ssym->name << ") at [" << start << ", " << (start + size - 1) << "]\n";
278 std::cout.flush();
279 #endif
280
281 // Mark stack location as used for all conflicting variables.
282 typename boost::graph_traits<SI_t>::adjacency_iterator n, n_end;
283 for(boost::tie(n, n_end) = boost::adjacent_vertices(v, SI); n != n_end; ++n)
284 if (!SI[boost::edge(v, *n, SI).first].alignment_conflict_only)
285 SI[*n].free_stack -= boost::icl::discrete_interval<int>::type(start, start + size);
286 else
287 SI[*n].alignment_conflicts.insert(boost::icl::discrete_interval<int>::type(start, start + size));
288 }
289
290 // Place a single variable on the stack greedily.
291 template <class SI_t>
color_stack_var_greedily(const var_t v,SI_t & SI,int alignment,int * ssize)292 void color_stack_var_greedily(const var_t v, SI_t &SI, int alignment, int *ssize)
293 {
294 int start;
295 symbol *const sym = SI[v].sym;
296 const int size = getSize(sym->type);
297
298 // Find a suitable free stack location.
299 boost::icl::interval_set<int>::iterator si;
300 for(si = SI[v].free_stack.begin();; ++si)
301 {
302 start = boost::icl::first(*si);
303
304 bool alignment_issue;
305 do
306 {
307 // Adjust start address for alignment conflict
308 std::set<boost::icl::discrete_interval<int> >::const_iterator ai, ai_end;
309 for(ai = SI[v].alignment_conflicts.begin(), ai_end = SI[v].alignment_conflicts.end(); ai != ai_end; ++ai)
310 {
311 if(ai->upper() < start || ai->lower() > start + size - 1)
312 continue;
313 if(ai->lower() == start)
314 continue;
315
316 #ifdef DEBUG_SALLOC
317 std::cerr << "Resolving alignment conflict at " << SI[v].sym->name << "\n";
318 #endif
319
320 start = ai->upper() + 1; // Resolve conflict.
321 }
322
323 // Adjust start address for alignment
324 alignment_issue = start % alignment;
325 if(start % alignment)
326 start = start + alignment - start % alignment;
327 }
328 while (alignment_issue);
329
330 if(boost::icl::last(*si) >= start + size - 1)
331 break; // Found one.
332 }
333
334 color_stack_var(v, SI, start, ssize);
335 }
336
337 static
get_alignment(sym_link * type)338 int get_alignment(sym_link *type)
339 {
340 #if 1
341 return(1);
342 #else
343 for(; IS_ARRAY (type); type = type->next);
344
345 switch(getSize(type))
346 {
347 case 0: // ?
348 case 1:
349 return(1);
350 case 2:
351 return(2);
352 case 3:
353 case 4:
354 return(4);
355 default:
356 return(8);
357 }
358 #endif
359 }
360
361 template <class SI_t>
chaitin_ordering(const SI_t & SI,std::list<var_t> & ordering)362 void chaitin_ordering(const SI_t &SI, std::list<var_t> &ordering)
363 {
364 std::vector<bool> marked(boost::num_vertices(SI));
365 unsigned int num_marked, i, d, mind, minn;
366 std::stack<var_t> stack;
367
368 for(num_marked = 0; num_marked < boost::num_vertices(SI); num_marked++)
369 {
370 mind = UINT_MAX;
371 minn = -1;
372 for(i = 0; i < boost::num_vertices(SI); i++)
373 {
374 if(marked[i])
375 continue;
376
377 typename boost::graph_traits<const SI_t>::adjacency_iterator n, n_end;
378 for(boost::tie(n, n_end) = boost::adjacent_vertices(i, SI), d = 0; n != n_end; ++n)
379 d += !marked[*n];
380
381 if(d < mind || d == mind && get_alignment(SI[i].sym->type) < get_alignment(SI[minn].sym->type)) // Coloring aligned variables first tends to keep gaps from alignment small.
382 {
383 mind = d;
384 minn = i;
385 }
386 }
387
388 stack.push(minn);
389 marked[minn] = true;
390 }
391
392 while(!stack.empty())
393 {
394 ordering.push_back(stack.top());
395 stack.pop();
396 }
397 }
398
399 template <class SI_t>
chaitin_salloc(SI_t & SI)400 void chaitin_salloc(SI_t &SI)
401 {
402 std::list<var_t> ordering;
403
404 chaitin_ordering(SI, ordering);
405
406 for(unsigned int i = 0; i < boost::num_vertices(SI); i++)
407 SI[i].free_stack.insert(boost::icl::discrete_interval<int>::type(0, 1 << 15));
408
409 int ssize = 0;
410
411 clearStackOffsets();
412
413 std::list<var_t>::const_iterator i, i_end;
414 for(i = ordering.begin(), i_end = ordering.end(); i != i_end; ++i)
415 {
416 // Alignment, even when not required by the hardware helps avoid partially overlapping stack operands (which are not supported by code generation in some backends).
417 color_stack_var_greedily(*i, SI, get_alignment (SI[*i].sym->type), &ssize);
418 }
419
420 if(currFunc)
421 {
422 if (TARGET_PDK_LIKE && (ssize % 2)) // Padauk requires even stack alignment.
423 ssize++;
424 #ifdef DEBUG_SALLOC
425 std::cout << "Function " << currFunc->name << " currFunc->stack: old " << currFunc->stack << ", new " << (currFunc->stack + ssize) << "\n";
426 #endif
427 currFunc->stack += ssize;
428 SPEC_STAK (currFunc->etype) += ssize;
429 }
430 }
431
432 static
dump_scon(const scon_t & scon)433 void dump_scon(const scon_t &scon)
434 {
435 if(!currFunc)
436 return;
437
438 std::ofstream dump_file((std::string(dstFileName) + ".dumpsalloccon" + currFunc->rname + ".dot").c_str());
439
440 std::string *name = new std::string[boost::num_vertices(scon)];
441 for(var_t i = 0; static_cast<boost::graph_traits<scon_t>::vertices_size_type>(i) < boost::num_vertices(scon); i++)
442 {
443 int start = scon[i].color;
444 std::ostringstream os;
445 os << i;
446 if (scon[i].sym->name)
447 os << " : " << scon[i].sym->name << " : " << getSize(scon[i].sym->type) << " [" << start << "," << (start + getSize(scon[i].sym->type) - 1) << "]";
448 name[i] = os.str();
449 }
450 boost::write_graphviz(dump_file, scon, boost::make_label_writer(name));
451 delete[] name;
452 }
453 #endif
454
455