Mercurial > projects > ldc

comparison gen/structs.cpp @ 1228:79758fd2f48a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added Doxygen file. Completely seperated type and symbol generation. Should fix a lot of bugs, but is not yet 100% complete.
author Tomas Lindquist Olsen <tomas.l.olsen gmail.com>
date Wed, 15 Apr 2009 20:06:25 +0200
parents ba9d6292572a
children 212ec2d9d176
comparison
equal deleted inserted replaced
1215:08f87d8cd101 1228:79758fd2f48a
13 #include "gen/arrays.h" 13 #include "gen/arrays.h"
14 #include "gen/logger.h" 14 #include "gen/logger.h"
15 #include "gen/structs.h" 15 #include "gen/structs.h"
16 #include "gen/dvalue.h" 16 #include "gen/dvalue.h"
17 #include "gen/functions.h" 17 #include "gen/functions.h"
18 #include "gen/utils.h"
18 19
19 #include "ir/irstruct.h" 20 #include "ir/irstruct.h"
20 21 #include "ir/irtypestruct.h"
21 //////////////////////////////////////////////////////////////////////////////////////////
22
23 // pair of var and its init
24 typedef std::pair<VarDeclaration*,Initializer*> VarInitPair;
25
26 // comparison func for qsort
27 static int varinit_offset_cmp_func(const void* p1, const void* p2)
28 {
29 VarDeclaration* v1 = ((VarInitPair*)p1)->first;
30 VarDeclaration* v2 = ((VarInitPair*)p2)->first;
31 if (v1->offset < v2->offset)
32 return -1;
33 else if (v1->offset > v2->offset)
34 return 1;
35 else
36 return 0;
37 }
38
39 /*
40 this uses a simple algorithm to build the correct constant
41
42 (1) first sort the explicit initializers by offset... well, DMD doesn't :)
43
44 (2) if there is NO space before the next explicit initializeer, goto (9)
45 (3) find the next default initializer that fits before it, if NOT found goto (7)
46 (4) insert zero padding up to the next default initializer
47 (5) insert the next default initializer
48 (6) goto (2)
49
50 (7) insert zero padding up to the next explicit initializer
51
52 (9) insert the next explicit initializer
53 (10) goto (2)
54
55 (11) done
56
57 (next can be the end too)
58
59 */
60
61 // return the next default initializer to use or null
62 static VarDeclaration* nextDefault(IrStruct* irstruct, size_t& idx, size_t pos, size_t offset)
63 {
64 IrStruct::VarDeclVector& defaults = irstruct->defVars;
65 size_t ndefaults = defaults.size();
66
67 // for each valid index
68 while(idx < ndefaults)
69 {
70 VarDeclaration* v = defaults[idx];
71
72 // skip defaults before pos
73 if (v->offset < pos)
74 {
75 idx++;
76 continue;
77 }
78
79 // this var default fits
80 if (v->offset >= pos && v->offset + v->type->size() <= offset)
81 return v;
82
83 // not usable
84 break;
85 }
86
87 // not usable
88 return NULL;
89 }
90
91 LLConstant* DtoConstStructInitializer(StructInitializer* si)
92 {
93 Logger::println("DtoConstStructInitializer: %s", si->toChars());
94 LOG_SCOPE;
95
96 // get TypeStruct
97 assert(si->ad);
98 TypeStruct* ts = (TypeStruct*)si->ad->type;
99
100 // force constant initialization of the symbol
101 si->ad->codegen(Type::sir);
102
103 // sanity check
104 assert(si->value.dim > 0);
105 assert(si->value.dim == si->vars.dim);
106
107 // vector of final initializer constants
108 std::vector<LLConstant*> inits;
109
110 // get the ir struct
111 IrStruct* irstruct = si->ad->ir.irStruct;
112
113 // get default fields
114 IrStruct::VarDeclVector& defaults = irstruct->defVars;
115 size_t ndefaults = defaults.size();
116
117 // make sure si->vars is sorted by offset
118 std::vector<VarInitPair> vars;
119 size_t nvars = si->vars.dim;
120 vars.resize(nvars);
121
122 // fill pair vector
123 for (size_t i = 0; i < nvars; i++)
124 {
125 VarDeclaration* var = (VarDeclaration*)si->vars.data[i];
126 Initializer* ini = (Initializer*)si->value.data[i];
127 assert(var);
128 assert(ini);
129 vars[i] = std::make_pair(var, ini);
130 }
131 // sort it
132 qsort(&vars[0], nvars, sizeof(VarInitPair), &varinit_offset_cmp_func);
133
134 // check integrity
135 // and do error checking, since the frontend does not verify static struct initializers
136 size_t lastoffset = 0;
137 size_t lastsize = 0;
138 bool overlap = false;
139 for (size_t i=0; i < nvars; i++)
140 {
141 // next explicit init var
142 VarDeclaration* var = vars[i].first;
143 Logger::println("var = %s : +%u", var->toChars(), var->offset);
144
145 // I would have thought this to be a frontend check
146 for (size_t j=i+1; j<nvars; j++)
147 {
148 if (j == i)
149 continue;
150 VarDeclaration* var2 = vars[j].first;
151 if (var2->offset >= var->offset && var2->offset < var->offset + var->type->size())
152 {
153 fprintf(stdmsg, "Error: %s: initializer '%s' overlaps with '%s'\n", si->loc.toChars(), var->toChars(), var2->toChars());
154 overlap = true;
155 }
156 }
157
158 // update offsets
159 lastoffset = var->offset;
160 lastsize = var->type->size();
161 }
162
163 // error handling, report all overlaps before aborting
164 if (overlap)
165 {
166 error("%s: overlapping union initializers", si->loc.toChars());
167 }
168
169 // go through each explicit initalizer, falling back to defaults or zeros when necessary
170 lastoffset = 0;
171 lastsize = 0;
172
173 size_t j=0; // defaults
174
175 for (size_t i=0; i < nvars; i++)
176 {
177 // get var and init
178 VarDeclaration* var = vars[i].first;
179 Initializer* ini = vars[i].second;
180
181 size_t offset = var->offset;
182 size_t size = var->type->size();
183
184 // if there is space before the next explicit initializer
185 Lpadding:
186 size_t pos = lastoffset+lastsize;
187 if (offset > pos)
188 {
189 // find the the next default initializer that fits in this space
190 VarDeclaration* nextdef = nextDefault(irstruct, j, lastoffset+lastsize, offset);
191
192 // found
193 if (nextdef)
194 {
195 // need zeros before the default
196 if (nextdef->offset > pos)
197 {
198 Logger::println("inserting %lu byte padding at %lu", nextdef->offset - pos, pos);
199 addZeros(inits, pos, nextdef->offset);
200 }
201
202 // do the default
203 Logger::println("adding default field: %s : +%u", nextdef->toChars(), nextdef->offset);
204 if (!nextdef->ir.irField->constInit)
205 nextdef->ir.irField->constInit = DtoConstInitializer(nextdef->loc, nextdef->type, nextdef->init);
206 LLConstant* c = nextdef->ir.irField->constInit;
207 inits.push_back(c);
208
209 // update offsets
210 lastoffset = nextdef->offset;
211 lastsize = nextdef->type->size();
212
213 // check if more defaults would fit
214 goto Lpadding;
215 }
216 // not found, pad with zeros
217 else
218 {
219 Logger::println("inserting %lu byte padding at %lu", offset - pos, pos);
220 addZeros(inits, pos, offset);
221 // offsets are updated by the explicit initializer
222 }
223 }
224
225 // insert next explicit
226 Logger::println("adding explicit field: %s : +%lu", var->toChars(), offset);
227 LOG_SCOPE;
228 LLConstant* c = DtoConstInitializer(var->loc, var->type, ini);
229 inits.push_back(c);
230
231 lastoffset = offset;
232 lastsize = size;
233 }
234
235 // there might still be padding after the last one, make sure that is defaulted/zeroed as well
236 size_t structsize = si->ad->structsize;
237
238 // if there is space before the next explicit initializer
239 // FIXME: this should be handled in the loop above as well
240 Lpadding2:
241 size_t pos = lastoffset+lastsize;
242 if (structsize > pos)
243 {
244 // find the the next default initializer that fits in this space
245 VarDeclaration* nextdef = nextDefault(irstruct, j, lastoffset+lastsize, structsize);
246
247 // found
248 if (nextdef)
249 {
250 // need zeros before the default
251 if (nextdef->offset > pos)
252 {
253 Logger::println("inserting %lu byte padding at %lu", nextdef->offset - pos, pos);
254 addZeros(inits, pos, nextdef->offset);
255 }
256
257 // do the default
258 Logger::println("adding default field: %s : +%u", nextdef->toChars(), nextdef->offset);
259 if (!nextdef->ir.irField->constInit)
260 nextdef->ir.irField->constInit = DtoConstInitializer(nextdef->loc, nextdef->type, nextdef->init);
261 LLConstant* c = nextdef->ir.irField->constInit;
262 inits.push_back(c);
263
264 // update offsets
265 lastoffset = nextdef->offset;
266 lastsize = nextdef->type->size();
267
268 // check if more defaults would fit
269 goto Lpadding2;
270 }
271 // not found, pad with zeros
272 else
273 {
274 Logger::println("inserting %lu byte padding at %lu", structsize - pos, pos);
275 addZeros(inits, pos, structsize);
276 lastoffset = pos;
277 lastsize = structsize - pos;
278 }
279 }
280
281 assert(lastoffset+lastsize == structsize);
282
283 // make the constant struct
284 LLConstant* c = LLConstantStruct::get(inits, si->ad->ir.irStruct->packed);
285 if (Logger::enabled())
286 {
287 Logger::cout() << "constant struct initializer: " << *c << '\n';
288 }
289 assert(getTypePaddedSize(c->getType()) == structsize);
290 return c;
291 }
292
293 //////////////////////////////////////////////////////////////////////////////////////////
294
295 std::vector<llvm::Value*> DtoStructLiteralValues(const StructDeclaration* sd, const std::vector<llvm::Value*>& inits)
296 {
297 // get arrays
298 size_t nvars = sd->fields.dim;
299 VarDeclaration** vars = (VarDeclaration**)sd->fields.data;
300
301 assert(inits.size() == nvars);
302
303 // first locate all explicit initializers
304 std::vector<VarDeclaration*> explicitInits;
305 for (size_t i=0; i < nvars; i++)
306 {
307 if (inits[i])
308 {
309 explicitInits.push_back(vars[i]);
310 }
311 }
312
313 // vector of values to build aggregate from
314 std::vector<llvm::Value*> values;
315
316 // offset trackers
317 size_t lastoffset = 0;
318 size_t lastsize = 0;
319
320 // index of next explicit init
321 size_t exidx = 0;
322 // number of explicit inits
323 size_t nex = explicitInits.size();
324
325 // for through each field and build up the struct, padding with zeros
326 size_t i;
327 for (i=0; i<nvars; i++)
328 {
329 VarDeclaration* var = vars[i];
330
331 // get var info
332 size_t os = var->offset;
333 size_t sz = var->type->size();
334
335 // get next explicit
336 VarDeclaration* nextVar = NULL;
337 size_t nextOs = 0;
338 if (exidx < nex)
339 {
340 nextVar = explicitInits[exidx];
341 nextOs = nextVar->offset;
342 }
343 // none, rest is defaults
344 else
345 {
346 break;
347 }
348
349 // not explicit initializer, default initialize if there is room, otherwise skip
350 if (!inits[i])
351 {
352 // default init if there is room
353 // (past current offset) and (small enough to fit before next explicit)
354 if ((os >= lastoffset + lastsize) && (os+sz <= nextOs))
355 {
356 // add any 0 padding needed before this field
357 if (os > lastoffset + lastsize)
358 {
359 //printf("1added %lu zeros\n", os - lastoffset - lastsize);
360 addZeros(values, lastoffset + lastsize, os);
361 }
362
363 // get field default init
364 IrField* f = var->ir.irField;
365 assert(f);
366 if (!f->constInit)
367 f->constInit = DtoConstInitializer(var->loc, var->type, var->init);
368
369 values.push_back(f->constInit);
370
371 lastoffset = os;
372 lastsize = sz;
373 //printf("added default: %s : %lu (%lu)\n", var->toChars(), os, sz);
374 }
375 // skip
376 continue;
377 }
378
379 assert(nextVar == var);
380
381 // add any 0 padding needed before this field
382 if (os > lastoffset + lastsize)
383 {
384 //printf("added %lu zeros\n", os - lastoffset - lastsize);
385 addZeros(values, lastoffset + lastsize, os);
386 }
387
388 // add the expression value
389 values.push_back(inits[i]);
390
391 // update offsets
392 lastoffset = os;
393 lastsize = sz;
394
395 // go to next explicit init
396 exidx++;
397
398 //printf("added field: %s : %lu (%lu)\n", var->toChars(), os, sz);
399 }
400
401 // fill out rest with default initializers
402 const LLType* structtype = DtoType(sd->type);
403 size_t structsize = getTypePaddedSize(structtype);
404
405 // FIXME: this could probably share some code with the above
406 if (structsize > lastoffset+lastsize)
407 {
408 for (/*continue from first loop*/; i < nvars; i++)
409 {
410 VarDeclaration* var = vars[i];
411
412 // get var info
413 size_t os = var->offset;
414 size_t sz = var->type->size();
415
416 // skip?
417 if (os < lastoffset + lastsize)
418 continue;
419
420 // add any 0 padding needed before this field
421 if (os > lastoffset + lastsize)
422 {
423 //printf("2added %lu zeros\n", os - lastoffset - lastsize);
424 addZeros(values, lastoffset + lastsize, os);
425 }
426
427 // get field default init
428 IrField* f = var->ir.irField;
429 assert(f);
430 if (!f->constInit)
431 f->constInit = DtoConstInitializer(var->loc, var->type, var->init);
432
433 values.push_back(f->constInit);
434
435 lastoffset = os;
436 lastsize = sz;
437 //printf("2added default: %s : %lu (%lu)\n", var->toChars(), os, sz);
438 }
439 }
440
441 // add any 0 padding needed at the end of the literal
442 if (structsize > lastoffset+lastsize)
443 {
444 //printf("3added %lu zeros\n", structsize - lastoffset - lastsize);
445 addZeros(values, lastoffset + lastsize, structsize);
446 }
447
448 return values;
449 }
450 22
451 ////////////////////////////////////////////////////////////////////////////////////////// 23 //////////////////////////////////////////////////////////////////////////////////////////
452 24
453 LLValue* DtoIndexStruct(LLValue* src, StructDeclaration* sd, VarDeclaration* vd) 25 LLValue* DtoIndexStruct(LLValue* src, StructDeclaration* sd, VarDeclaration* vd)
454 { 26 {
488 return val; 60 return val;
489 } 61 }
490 62
491 ////////////////////////////////////////////////////////////////////////////////////////// 63 //////////////////////////////////////////////////////////////////////////////////////////
492 64
493 static void DtoDeclareStruct(StructDeclaration* sd);
494 static void DtoConstInitStruct(StructDeclaration* sd);
495 static void DtoDefineStruct(StructDeclaration* sd);
496
497 void DtoResolveStruct(StructDeclaration* sd) 65 void DtoResolveStruct(StructDeclaration* sd)
498 { 66 {
499 // don't do anything if already been here 67 // don't do anything if already been here
500 if (sd->ir.resolved) return; 68 if (sd->ir.resolved) return;
501 // make sure above works :P 69 // make sure above works :P
503 71
504 // log what we're doing 72 // log what we're doing
505 Logger::println("Resolving struct type: %s (%s)", sd->toChars(), sd->locToChars()); 73 Logger::println("Resolving struct type: %s (%s)", sd->toChars(), sd->locToChars());
506 LOG_SCOPE; 74 LOG_SCOPE;
507 75
508 // get the DMD TypeStruct 76 // make sure type exists
509 TypeStruct* ts = (TypeStruct*)sd->type; 77 DtoType(sd->type);
510 78
511 // create the IrStruct 79 // create the IrStruct
512 IrStruct* irstruct = new IrStruct(sd); 80 IrStruct* irstruct = new IrStruct(sd);
513 sd->ir.irStruct = irstruct; 81 sd->ir.irStruct = irstruct;
514 82
515 // create the type 83 // emit the initZ symbol
516 ts->ir.type = new LLPATypeHolder(llvm::OpaqueType::get()); 84 LLGlobalVariable* initZ = irstruct->getInitSymbol();
517 85
518 // create symbols we're going to need 86 // perform definition
519 // avoids chicken egg problems 87 if (mustDefineSymbol(sd))
520 std::string initname("_D");
521 initname.append(sd->mangle());
522 initname.append("6__initZ");
523
524 llvm::GlobalValue::LinkageTypes _linkage = DtoExternalLinkage(sd);
525 sd->ir.irStruct->init = new llvm::GlobalVariable(sd->ir.irStruct->initOpaque.get(), true, _linkage, NULL, initname, gIR->module);
526
527 // handle forward declaration structs (opaques)
528 // didn't even know D had those ...
529 if (sd->sizeok != 1)
530 { 88 {
531 // nothing more to do 89 // set initZ initializer
532 return; 90 initZ->setInitializer(irstruct->getDefaultInit());
533 } 91 }
534 92
535 // make this struct current 93 // emit members
536 gIR->structs.push_back(irstruct); 94 if (sd->members)
537 95 {
538 // get some info 96 ArrayIter<Dsymbol> it(*sd->members);
539 bool ispacked = (ts->alignsize() == 1); 97 while (!it.done())
540 98 {
541 // set irstruct info 99 Dsymbol* member = it.get();
542 irstruct->packed = ispacked; 100 if (member)
543 101 member->codegen(Type::sir);
544 // methods, fields 102 it.next();
545 Array* arr = sd->members; 103 }
546 for (int k=0; k < arr->dim; k++) {
547 Dsymbol* s = (Dsymbol*)arr->data[k];
548 s->codegen(Type::sir);
549 } 104 }
550 105
551 const LLType* ST = irstruct->build();
552
553 #if 0
554 std::cout << sd->kind() << ' ' << sd->toPrettyChars() << " type: " << *ST << '\n';
555
556 // add fields
557 for (int k=0; k < fields->dim; k++)
558 {
559 VarDeclaration* v = (VarDeclaration*)fields->data[k];
560 printf(" field: %s %s\n", v->type->toChars(), v->toChars());
561 printf(" index: %u offset: %u\n", v->ir.irField->index, v->ir.irField->unionOffset);
562 }
563
564 unsigned llvmSize = (unsigned)getTypePaddedSize(ST);
565 unsigned dmdSize = (unsigned)sd->type->size();
566 printf(" llvm size: %u dmd size: %u\n", llvmSize, dmdSize);
567 assert(llvmSize == dmdSize);
568
569 #endif
570
571 /*for (int k=0; k < sd->members->dim; k++) {
572 Dsymbol* dsym = (Dsymbol*)(sd->members->data[k]);
573 dsym->toObjFile();
574 }*/
575
576 Logger::println("doing struct fields");
577
578 // refine abstract types for stuff like: struct S{S* next;}
579 llvm::cast<llvm::OpaqueType>(ts->ir.type->get())->refineAbstractTypeTo(ST);
580 ST = ts->ir.type->get();
581
582 // name type
583 if (sd->parent->isModule()) {
584 gIR->module->addTypeName(sd->mangle(),ST);
585 }
586
587 // emit functions
588 size_t n = irstruct->structFuncs.size();
589 for (size_t i = 0; i < n; ++i)
590 {
591 DtoResolveFunction(irstruct->structFuncs[i]);
592 }
593 irstruct->structFuncs.clear();
594
595 gIR->structs.pop_back();
596
597 DtoDeclareStruct(sd);
598 }
599
600 //////////////////////////////////////////////////////////////////////////////////////////
601
602 static void DtoDeclareStruct(StructDeclaration* sd)
603 {
604 DtoResolveStruct(sd);
605
606 if (sd->ir.declared) return;
607 sd->ir.declared = true;
608
609 Logger::println("DtoDeclareStruct(%s): %s", sd->toChars(), sd->loc.toChars());
610 LOG_SCOPE;
611
612 TypeStruct* ts = (TypeStruct*)sd->type->toBasetype();
613
614 DtoConstInitStruct(sd);
615 if (mustDefineSymbol(sd))
616 DtoDefineStruct(sd);
617 }
618
619 //////////////////////////////////////////////////////////////////////////////////////////
620
621 static void DtoConstInitStruct(StructDeclaration* sd)
622 {
623 DtoDeclareStruct(sd);
624
625 if (sd->ir.initialized) return;
626 sd->ir.initialized = true;
627
628 Logger::println("DtoConstInitStruct(%s): %s", sd->toChars(), sd->loc.toChars());
629 LOG_SCOPE;
630
631 IrStruct* irstruct = sd->ir.irStruct;
632 gIR->structs.push_back(irstruct);
633
634 const llvm::StructType* structtype = isaStruct(sd->type->ir.type->get());
635
636 // always generate the constant initalizer
637 assert(!irstruct->constInit);
638 if (sd->zeroInit)
639 {
640 Logger::println("Zero initialized");
641 irstruct->constInit = llvm::ConstantAggregateZero::get(structtype);
642 }
643 else
644 {
645 Logger::println("Not zero initialized");
646
647 LLConstant* c = irstruct->buildDefaultConstInit();
648 irstruct->constInit = c;
649 }
650
651 // refine __initZ global type to the one of the initializer
652 llvm::cast<llvm::OpaqueType>(irstruct->initOpaque.get())->refineAbstractTypeTo(irstruct->constInit->getType());
653
654 // build initializers for static member variables
655 size_t n = irstruct->staticVars.size();
656 for (size_t i = 0; i < n; ++i)
657 {
658 DtoConstInitGlobal(irstruct->staticVars[i]);
659 }
660 // This is all we use it for. Clear the memory!
661 irstruct->staticVars.clear();
662
663 gIR->structs.pop_back();
664
665 // emit typeinfo 106 // emit typeinfo
666 if (sd->getModule() == gIR->dmodule && sd->llvmInternal != LLVMno_typeinfo) 107 DtoTypeInfoOf(sd->type);
667 DtoTypeInfoOf(sd->type, false);
668 }
669
670 //////////////////////////////////////////////////////////////////////////////////////////
671
672 static void DtoDefineStruct(StructDeclaration* sd)
673 {
674 DtoConstInitStruct(sd);
675
676 if (sd->ir.defined) return;
677 sd->ir.defined = true;
678
679 Logger::println("DtoDefineStruct(%s): %s", sd->toChars(), sd->loc.toChars());
680 LOG_SCOPE;
681
682 assert(sd->type->ty == Tstruct);
683 TypeStruct* ts = (TypeStruct*)sd->type;
684 sd->ir.irStruct->init->setInitializer(sd->ir.irStruct->constInit);
685
686 sd->ir.DModule = gIR->dmodule;
687 } 108 }
688 109
689 ////////////////////////////////////////////////////////////////////////////////////////// 110 //////////////////////////////////////////////////////////////////////////////////////////
690 //////////////////////////// D STRUCT UTILITIES //////////////////////////////////// 111 //////////////////////////// D STRUCT UTILITIES ////////////////////////////////////
691 ////////////////////////////////////////////////////////////////////////////////////////// 112 //////////////////////////////////////////////////////////////////////////////////////////