2 Bug: dominator construction aborts for BreakTest with flag 3.31
3 Problem: optimization of many subsequent blocks (Jmp-chains)
4 where one is inlined (Tuple control flow) in a loop. Not all
5 nodes in merged blocks are moved to remaining block.
6 Fix: different calling order to optimize_in_place_2 from
7 optimize_in_place_wrapper.
8 Bug: dumping cfg when a block is Bad. Fix: Output Bad node.
9 Change: not only turn off cse but all optimizations during
13 Parted common.h into two files common_t.h. By this config.h
14 as well as the preprocessor flags are no more visible externaly.
15 Adapted include directives.
18 Bugfix in inlining: problems in combination with cse.
21 Implemented cf optimizations.
22 Checked compiler flags -- sorted better to fit optimizations.
26 Implemented code placement.
30 irdom implemented: dominator information.
33 Bugfix Optmierung Binops mit mode Tupel.
36 irgopt: inline_small_irgs implemented
39 Bugfixes, some access functions ...
42 New directory: ana for analyses. Adapted configure/makefiles
43 implemented irout: backedges. Added one field to ir_graph, one to ir_node.
44 Implemented state management for irgraphs: see irgraph.h.
45 Must now call finalize_cons() after graph construction!!
49 Flag pinned in irop, irgraph.
50 Global cse in irop, setting the irgraph flag.
51 Example programs: Endless_loop.c. global_cse.c.
55 Implemented support for endless loops:
57 Adapted Phi constructors so that memory phis are added.
58 Adapted Cond optimization: add block to End.
59 Adapted dead node elimination: compation of Ends predecessors
60 Adapted inlineing: remember keepalives of inlined graph.
61 Added informative strings to asserts in irvrfy.
64 Added volatile flag to entity, order flag to array.
65 Added a set of assertions.
68 Added access function set_class_members()
71 Asserts in irvrfy that verify the mode of Proj nodes. For Start,
72 Call, Return they check the corresponding function type! Corrected
74 Some asserts for legal values of 'pos' arguments in type/entity
78 Some access routines for visited flags in entity.h, irnode.h,
79 bug in oo_program_example.
82 Removed all obsolete Makefiles
85 Added support for constant entities. A new example program illustrates
86 their use. Extended dumper routines to dump constant values.
89 Extendend "comfortable" construction interface by some methods
90 serving as simple shortcuts.
93 Added a class type to irgs. This class type is to be used as owner
94 for local entities of the procedure. This are all entities allocated
95 for each execution of the procedure.
96 The class type is allocated automatically by new_ir_graph(). Access
97 routines to get this type are in irgraph.h.
98 We chose a class type as this allows to represent "inner" procedures
100 Adapted array-stack-example.
103 irdump outputs nodeids instead of pointers for labels of nodes.
104 With a preprocessor flag in common.h this can be turned off.
107 Added an Id tag to every .c and .h file
110 Changed SSA constuction for exception control flow.
111 If PRECISE_EXC_CONTEXT is used Phi nodes will use the values
112 valid when the execption operation was allocated. This increases
113 the memory consuption of the construction algorithm by
114 n_loc * #fragile_ops.
117 Added method to replace in array of a node in irnode.c/h
118 Added functionality to irgmod:
119 * collect all Phi nodes as link-list in the Blocks link field
120 * collect all Proj nodes as link-list in node producing the tuple.
121 * Seperate a Block into two
122 Added inlining transformation in irgopt.h
123 Improved output of dump_ir_block_graph. Now also dumps nodes that
124 don't belong to a block.
125 Added flag opt_unreachable_code, opt_inline.
126 Changed irvrfy so that it accepts nodes with Bad predecessors.
129 renamed get_type_nameid to get_type_ident
132 Bugfix: dead node elimination did not replace the hash table
136 Added routine remove_irp_irg.
137 Changed comment to free_ir_graph.
140 Added routine to free irgraphs.
143 Improved add routines to sub, supertype in type.c
146 Added implementation of overwrites stuff.
149 Implemented stuff to change the type graph. See
150 typegmod.h and tpop.h for basic documentation of the change.
151 There now exists a type of kind type_id. If this appears
152 externally this is a bug.
155 Added some new access routines to types.
156 List of overwritten fields for entities.
157 Removed a bug in irnode.
160 Added a routine to set the mangled entity name.
161 Added two routines to copy entites.
164 Entities now have two more flags, for visibility and allocation mode.
165 Types that have a layout have a flag indicating whether the layout is
169 We distinguish three kinds of Cond nodes. These can be distinguished
170 by the mode of the selector operand and an internal flag of type cond_kind.
171 First we distinguish binary Conds and switch Conds.
172 A binary Cond has as selector a boolean value. Proj(0) projects the control
173 flow for case "False", Proj(1) the control flow for "True". A binary Cond
174 is recognized by the boolean selector.
175 The switch Cond has as selector an unsigned integer. It produces as result
176 an n+1 Tuple (cf0, ... , cfn) of control flows.
177 We differ two flavours of this Cond. The first, the dense Cond, passes
178 control along output i if the selector value is i, 0 <= i <= n. If the
179 selector value is >n it passes control along output n.
180 The second Cond flavor differes in the treatment of cases not specified in
181 the source program. It magically knows about the existence of Proj nodes.
182 It only passes control along output i, 0 <= i <= n, if a node Proj(Cond, i)
183 exists. Else it passes control along output n (even if this Proj does not
184 exist.) This Cond we call "fragmentary". There is a special constructor
185 new_defaultProj that automatically sets the flavor.
186 The two switch flavors are distinguished by a flag of type cond_kind.
187 Default flavor is "dense"
191 tv now implements Minus, Abs.
192 iropt now optimizes these and Div, Mod, Quot, DivMod.
193 Still missing: Shrs, Rot.
194 tarval_shr somtimes performs shrs, depending on the compiler/system!!
195 If the ArmRoq implementation is faulty there might appear errors.
198 Changed ircons: If undefined values are used the Phi construction
199 inserts a constant with value tarval_bad.
202 Changed array bounds in type.h to ir_node*. This allows to
203 construct array bounds that are complex constant expressions
204 simpler. Further dynamic array bounds can be displayed.
205 Comment in ircons.c extended: undefined values in start_block.
208 ifdef'ed all uses of gmp in tv.c away. Optimizations for
209 mode_Z no more supported, as well as constants of that mode.
212 Dokumentation in ir_dump
213 Habe Routinen fuer einzelne Knoten/Kanten aus header entfernt:
214 Benutzen globale Variable die nicht oeffentlich zugaenglich ist.
217 We need an entity for the array elements for the Sel nodes. This
218 entity should be stored in the array type. Changed constructor
219 parameters: include array element type. Entity for elements is built
224 Faulty use of va_arg, became visible with new, stricter gcc 2.96.
227 Added list of member entites to union. unioned_types and delimiters
228 are superfluous now -- removed.
229 Rationale: we want to express selection of a union member as a Sel
230 node. for this we need to have entities. The entities contain the
231 unioned type and have as name the delimiters...
234 Changed Makefile/MakeTargets to install headers and libraries
238 Changed Makefile and Configure scripts to produce a proper tar file
239 for distribution (libfirm-VERSION.tar)
240 Use 'make distrib' instead of 'make dist'
243 Changed implementation of tr module. With this I also changed the
244 interface!! Type casts are unnecessary now, but some access funcions
248 ======================================================================
249 ==================== New version: 0.3.0 ==============================
250 ======================================================================
256 added creation of a tar archive for distribution
257 replaced ir/.dummy.in by ir/Makefile.in
260 Changed equivalent_node() and copy_preds() so that the end block
261 is not optimized away if it has no real predecessors. This fixes
262 the problem with the while examples.
263 Added while_example in Makefile
266 Fooled around with if_while_example: Why does cse make it abort?
267 Cse removes path to End node, Bad remains as pred of Endblock.
268 The block walker can't deal with this.
269 Made new example with only loop: while_example.
272 added auto documentation in Makefiles, configure, etc
273 example in ir/ir/ircons.c - much must be added
274 creation of documentation by 'make autodoc' in architecture directory
277 added lots of #ifdef HAVE_CONFIG_G #include "config.h" #endif
278 replaced some C++ style comments (//) by standard C comments /**/
281 - configure (with some features, see --help for more)
282 - make [depend | tags | install]
283 - make [run] in testprograms
285 - compilation on SunOS
287 - automatic call of autoconf if required
290 More colours in vcg output.
291 Fixed bug: cse found that start block equals it's
292 first successor as both have the Start block as predecessor.
293 This only happens for local_optimize_graph() as during construction
294 the Start block is not entered in the value table.
295 Changed implementation: irgmod: local_optimize_graph() did not
296 empty the hash table with the irnodes for cse. This might cause that
297 cse turns up with a node that seems better but was removed from the
298 graph in an earlier optimization phase.
299 Removed old #if 1 from ircons.c
300 Commented in call of optimization for Block nodes in irgopt.c, copy_preds():
301 Optimizes blocks that had bad predecessors.
306 Moved struct from irprog.h to irprog_t.h, same for irmode.h.
307 Added a module deb_info in debug.h. Adapted makefile. Added example
309 Removed use of debug.h in ident.c. Now debug.c|h can be moved to
311 Removed inabled code for dead node elimination in irgopt.h.
312 Renamed some missnamed access routines (_of_). Macros with old names
313 are in old_fctnames.h.
314 Edited makefiles to remove #* and *.flc.
317 Some minor bugfixes...
320 After compacting of in arrays in dead_node_elimination
321 merge blocks and remove Phis with one pred.
324 Freeing of obstack in dead_node_elimination commented in.
325 Compacting in arrays of Block and Phi nodes in dead_node_
330 added set/get_SymConst_type_or_id in irnode.h
331 added field offset to entity in entity.h
332 added field size to type_class in type.h
333 include "gmp.h" in tv.h with "" instead <>
336 Some changes to make the lib better portable
339 Initialize max_node_nr in irprog.
342 Now outputs warning if faulty type in irdump, dump_type_info.
343 Explicit string termination in irdump, vcg_open.
346 Added external to declaration of irp.
347 Added typedef before pns and pnc_number.
348 irmode.c, init_mode(): We need to memset all new modes as
349 tarval_vrfy reads fields before they are initialized: It
350 compares to min/max when tarvals for min/max are allocated!
353 Changed parameter of Methods in type.h and type.c from
354 class to clss. Class is a C++ keyword.
357 Changed some testprograms to accomodate Uebprakt.
360 Finished implementation of dump_all_types.
361 Added new testprogram inheritance_example.
364 Added seven access routines in type.[hc]:
365 get_class_n_member, get_class_n_subtype, get_class_n_supertype,
366 get_strct_n_member, add_strct_member, get_strct_member and set_strct_member.
367 Fixed the type_walk_2 for those seven routines.
370 Added irdump routine dump_all_types.
371 Did changes to irprog, type, typewalk to achieve this.
372 typewalk needs to walk along members, sub and supertypes, this
373 is still missing! irdump then needs to output these edges.
375 ======================================================================
376 ==================== New version: 0.2.5 ==============================
377 ======================================================================
380 Made new Version: 0.2.5
382 15.8.2000 Goetz until 3.9.00
383 Separated irnode.h and many others into two files: one public
385 Added funcionality to extract headers for lib.
388 type_dump also dumps irg->ent
389 if_example: corrected nr of locals
392 irgopt: Correct copy of self pointer in start block.
393 irgopt: Correct treatment of loops: pre function in walker
394 breaks all possible loops in Phi and Block nodes.
395 irr_loop_example: wrong Return statement
396 Now I fixed all but one error: in memory_example.
397 This error showed a conceptual problem, so I wrote
398 a slightly different algorithm. This now runs for
400 dead_node_example: cse is buggy!! merges start and the
404 looking at bug in dead_node_elimination.
406 irnode: all get_..._arr functions changed
407 ircons: new_r_Block: set matured flag.
408 ircons: new_r_SymConst: needs mode_p for linkage_ptr_info.
409 adapted call_str_example to new concepts.
412 Implemented simpler Phi construction algorithm that constructs
413 correct code for three_cfpred_example in ircons. This algorithm
414 generates more Id nodes than the original algorithm and therefore
416 Also made some changes to optimizations of Not.
419 Fixed a bug, caused by the recursive use in type.h and entity.h.
420 Deleted the _TYPE_TYPEDEF_ and inserted the _ENTITY_TYPEDEF_ instead.
421 Fixed a problem in if_while testprogram, so it now works.
424 Fixed bug in optimize(). Returned Null instead n if
425 get_optimize() == false.
428 Added some access routines in type.[hc]. Solved a recursive definition
429 of type_class struct, entity struct and type union.
432 Separated entity header into pure functional header and header
436 ... a bunch small changes not documented
439 Changed output of oo_prog_example: now uses the internal list
440 of all irgs. Had to implement some of the access routines for
441 that. Also fixed a bug in irdump. Main routines did not use
442 current_ir_graph properly.
445 Implemented some missing parts in irgopt.
446 Added field irg to entity. Only valid if entity is a method.
447 Had to resove a cyclic de[endency between irgraph.h and entity.h
449 Added fields sub and super to type_class for inheritance.
450 Added field main_irg to irprog.
453 Fixed some bugs in irgopt.c
454 Added some missing 'get_new_node' methods, so the new obstack contains
458 Renamed ir_vrfy to irn_vrfy and vrfy_graphg to irg_vrfy.
459 Solved some copy'n'paste problems. Deleted most debug-code!
460 Added comments to several files.
463 Fixed bug in _r_ constructors for all four Div operations.
464 Fixed bug in turn_into_tuple: didn't remember the block.
465 Tested transform_node.
468 Fixed some testprograms to new semantics of firm.
469 Added testprogram global_var_example.
470 Fixed a bug in irop: Size of Sel node was (entity *) instead of
471 sel_attr. Therefor array_heap_example aborted.
472 Also found a missing break in typewalk, case iro_Alloc.
473 Added a construct that unifies all things constructed by the lib
474 and needed to represent a program: irprog.ch
475 This contains a list of all types as well as a list of all ir graphs.
476 I added calls to initialization and constructors so that this is constructed
477 automatically. I changed firm.c, type.c, irgraph.c and ev. more.
478 Removed strange block struct and constructor from ircons.c.
479 Moved routines for automatic Phi construction from irgmod to ircons.
480 Sorted functions in ircons to reflect the different interfaces.
481 Renamed dataseg to globals to be conformant with documentation.
482 Added conservation of current_ir_graph to irgopt.c.
483 Corrected bug in Makefiles: wrong path to directory ./inlude.
486 Commented a whole bunch of stuff, e.g. in ircons.h (Procedure to construct)
487 We should change the naming of the Block constructor.
488 Removed acces routines to attr. "closed" of Block.
489 Removed second implementation of new_ir_node from ircons and some comments
490 concerned with the now resolved cyclic dependency.
491 Fixed some bugs in irgopt so that the compilation goes through.
494 Changed the irnode attribut 'visit' into 'visited'.
495 Added some access functions, like get/set_irn_visit etc.
498 Renamed some access funtion in irgraph.*.
499 Deleted two global flags (ir_visited and block_visited) from irgraph.*.
500 Added two attributes to the irgraph struct. The visited flags belongs
501 to a ir graph, not to a whole program.
504 A new optimization has been finished. The dead-node-elimination copies
505 the existing ir graph from one opstack to another. While walking the
506 graph, only the reachable nodes will be copied, so the "dead-nodes"
507 (unreachable in the controlflow) are removed.
510 Solved some problems in the 'copy_node' function. The in array was not
511 as easy as it seamed.
514 Wrote a new 'post' funtion, for future use in 'dead-node-elimination'
515 optimization, which is needed in the paramter list of 'irg_walk'.
518 Moved 'optimze_in_place_wrapper' from iropt.* tothe new files irgopt.*.
519 New functions 'local_optimze_graph' and 'dead_node_elimination' are added,
523 Removed some files from the archive, after dependencies and usage are
525 - 'ir/common/strerror.c'
527 - 'ir/ident/xx_ident.h'
528 an empty file, only included by 'ident.c', but never used;
529 - 'ir/tv/label.c' and
531 contained a numeric counter;
532 The files were included in 'tv.h' and implemented in 'tarval.c'. The two
533 functions 'tarval_label' and 'tarval_forall_labeled' were also never used.
534 In the old fiasco compiler, the label thing is used in the backend.
535 Search for 'babil' to see the usage.
536 Also removed the two attributes 'lab' and 'used' in the tarval struct.
539 Moved the 'new_ir_node' constructor from ircons.* to irnode.* and fixed
540 afterwards some recursive includes, so libfirm works again.
543 Did a lot of changes, which I never commented until now (4.7.00).
545 * Added new result to Start node: Pointer to global data segment.
546 * Extended Semantics of SymConst node to represent information for the
548 * Added arithmeitc nodes (Shrs, Minus ...)
550 Rearranged the directory structure and adjusted the makefiles.
551 The directories contain:
552 ir: everything for the intermediate representation (better: src?)
553 /ir: the ir itself, and standard optimizations.
554 /tv: the target value module
555 /tr: the type and entity representation
556 /adt: abstract data types
557 /common: stuff needed by all other dirs
558 /debug: debugging Unterstuetzung
560 include: external files needen as includes
561 testprograms: examples to test the lib.
563 The makefiles generate files with extension .d that contain the dependencies
567 Added access routine to attribute link of irnode in irnode.ch.
568 Added get_negated_pnc to irnode.ch.
571 Added an iterator in iropt that calls the optimization for all nodes.
572 Copied optimize's code to optimize_in_place and removed deallocations.
573 Made set_irn_n in irnode.c public.
574 Added Bad as possible cfg predecessor in is_cfg_node in irnode. Bads
575 are allowded as cfgpredecessors to represent dead "incoming" control
577 Added call to optimize_in_place in mature_block. Is this useful?
580 Changed tests from comparing enums to comparing pointers. This is more
581 efficient (is it?) and reads better. e.g., instead get_irn_opcode == irm_And
582 now get_irn_op == op_And
585 Compared equivalent_value to the one in the original fiasco.
586 Added a test in case iro_And.
587 Changed implementation of iro_Div. Added routines turn_into_tuple
588 and set_irn_op() in irgmod/irnode.
589 Changed implementation of irn_Minus (although commented out).
590 Now all features are ported or documented for this function.
593 Compared computed_value to the one in the original fiasco.
594 Added one further optimization in case iro_Proj.
595 Now all features are ported for this function.
598 Updated comments in ircons.h.
601 Changed possible attribute of SymConst from type_class to type.
602 SymConst size could be the size of a union, array, ...
605 Implemented two dumpers that dump type information and a graph with
609 Implemented a walker that walks over the type informatin that can
610 be reached from an ir node.
611 Added routine get_kind(firm_thing) in common.h, Added file common.c.
612 Added files typewalk.ch and routines to irdump.
613 Added visited flags and initialization to entity and all types.
614 Implemented some of the missing access routines in type.c, entity.c
617 Implemented constructor for ShrA.
619 Added routine that iterates the graph and verifies all nodes.
620 Added Phi_in stack to irgraph. This allows to build several
621 graphs at once with respect to the Phi building algorithm.
624 Implemented dumper for control flow graphs. Changed irr_* and dead_*
625 examples to dump cfg.
628 Implemeted explicit stack for the Phi node generation. See ircons.c.
631 added include string.h in xoprintf.c to get rid of warning:
632 implicit declaration of function `bcopy'
636 Added more cases to equivalent_node.
637 Portet gigo, identify, identify_remember.
638 The set/pset library can not handle several hash tables. At least,
639 compiling several procedures causes a segmentation fault during access
640 to the tables (oo_program_example). Need to work on this.
641 transform_node still needs to be ported.
642 some cases in equivalent_node are still missing.
644 To get it running I had to remove the call to optimize in the
645 new_Block constructor. It can only be called when the Block is
649 Introduced a walker that walks only over blocks. The asserts
650 might be too strict for general graphs, but so far it works.
651 For the walker I introduced an additional flag in the attribute
652 of Blocks, an a global block_visited variable (in irgraph.h).
653 Furhter I modularized dump_ir_node, implemented dump_ir_graph
654 with the existing walker, and added new routines to output a
656 Changed the examples to call the new dump routine.
659 Added auxiliary routines to ir_node:
660 skip_Proj, skip_Nop, is_Bad ...
661 Changed access routines to use get_irn_n instead of explicit array
662 accesses. Changed get_irn_n to call skip_Id, so that the access routines
663 never will return Id nodes.
666 Repaired Phi computation, changed new_r_Phi_in. Added test program to
667 test irregular controlflow.
670 Updated optimizations computed_value and equivalent_node to new
671 Syntax of FIRM nodes and to use access routines.
672 Added routine skip_Proj in irnode.
674 2.2.2000 Boris Boesler
675 Added files irgwalk.c and irgwalk.h. They include a simple function to
676 traverse an ir graph and execute pre and post functions to current node.
679 Added arrays with parameters and result types to the type informtion
680 of a procedure. This is needed for the code generation. Also added
681 the corresponding access routines.
682 Adapted the testprograms.
685 Found a bug / complication: the call order
686 get_value (makes Phi0, put's it into graph_arr)
687 set_value (overwrites Phi0 in graph_arr)
688 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
690 fails. Added test wether graph_arr is already set in phi_merge.
692 Added tons of comments to explain Phi generation -- the stack hack.
696 irdump now outputs the pnc_number for projs of Cmp nodes.
697 Added routine to access the pnc_string.
700 Added result "dataseg" to Start node, with all it's consequences.
701 We need this for the compiler lab to translate global variables.
702 Now they can be selected from the data segment, and the start
703 node supplies the pointer to this segment.
704 These changes are guarded by preprocessor variable UEBPRAKT in
706 Changed files: common.h, irgraph.ch, irnode.h
710 removed array_example, added array-heap_example and
711 array-stack_example and adapted makefile.
713 Entity now also allows type_method as owner. This is to model
714 the stack, Sel nodes that select a variable (array) from the
715 stack need an entity that describes what they select. This
716 entity gets the type of the enclosing procedure as owner.
719 Added future access routines in `irmode.[ch]' as comments,
720 that all attributes in the ir_mode struct can be user-defined.
721 Added access routines in `irgraph.[ch]', for all attributes.
724 Moved verify routines from `irgraph.[ch]' to own files `irvrfy.[ch]'.
725 Added `irvrfy.[ch]' to MAKEFILE
726 Added "inline" before access routines in `irnode.h', that no warnings
727 will appear furthermore.
728 Added three more access routines in `irmode.[ch]':
729 struct tarval *get_min_of_mode (ir_mode *mode);
730 struct tarval *get_max_of_mode (ir_mode *mode);
731 struct tarval *get_null_of_mode (ir_mode *mode);
734 Adaption of Alloc, Sel and Entity to new types:
735 Changed array_example to use type instead of type_class.
736 Changed entity to allow all types as owner instead of
737 only type_class. Added routine "assert_legal_owner_of_ent(type* type)".
738 Changed alloc to allow allocating variables of any type instead of
740 Adapted all testprograms to avoid warnings.
742 removed dtest ... from Makefile, replaced by test.
745 Added "run" to makefile, added array_example to makefile of testprograms.
746 Corrected testprogram array
747 Changed assert in irvrfy -- Conv.
projects / libfirm / blob