11213 Commits

Author SHA1 Message Date
Morgan Phillips
367752be1d Replace btreesets with vectors. 2016-07-21 22:44:13 -07:00
Morgan Phillips
4de89a7f96 Cargo-fmt fixes 2016-07-21 15:24:07 -07:00
Morgan Phillips
bdab73b0c7 Cargo-fmt fixes 2016-07-21 15:24:07 -07:00
Morgan Phillips
5037cc4db6 Add support for postorder traversal of the cfg. 2016-07-21 15:22:27 -07:00
Morgan Phillips
761fb54d8a Add support for postorder traversal of the cfg. 2016-07-21 15:22:27 -07:00
Morgan Phillips
a4126108a0 Track predecessors as well as successors in the CFG 2016-07-21 12:36:51 -07:00
Morgan Phillips
30eb25d013 Track predecessors as well as successors in the CFG 2016-07-21 12:36:51 -07:00
Morgan Phillips
505d49ec41 Use EntityMap instead of BTreeMap 2016-07-21 12:08:02 -07:00
Morgan Phillips
2caa802f50 Use EntityMap instead of BTreeMap 2016-07-21 12:08:02 -07:00
Jakob Stoklund Olesen
28069ff2a0 Move IR modules under repr/.
Use the cretonne::repr module as a common namespace for sub-modules defining the
in-memory representation of Cretonn IL.
2016-07-19 14:10:30 -07:00
Jakob Stoklund Olesen
89ba9626c7 Move IR modules under repr/.
Use the cretonne::repr module as a common namespace for sub-modules defining the
in-memory representation of Cretonn IL.
2016-07-19 14:10:30 -07:00
Jakob Stoklund Olesen
d20fe25f33 Prepare for repr sub-modules. 2016-07-19 13:53:02 -07:00
Jakob Stoklund Olesen
6e04ec5df9 Prepare for repr sub-modules. 2016-07-19 13:53:02 -07:00
Jakob Stoklund Olesen
28804e0b41 Use DataFlowGraph in Function.
Replace the three tables instructions, extended_basic_blocks, and
extended_values with a single 'dfg' public member.

Clients using Function are changed to refer to func.layout and func.dfg
respectively.
2016-07-19 13:05:28 -07:00
Jakob Stoklund Olesen
c1806d0ab0 Use DataFlowGraph in Function.
Replace the three tables instructions, extended_basic_blocks, and
extended_values with a single 'dfg' public member.

Clients using Function are changed to refer to func.layout and func.dfg
respectively.
2016-07-19 13:05:28 -07:00
Jakob Stoklund Olesen
8a55ed59de Implement separate data flow graph module.
The DFG keeps track of instruction definitions, values, and EBBs.

Store the primary definition of each instruction: Opcode and operands.
Track SSA values as either the result of an instruction or EBB arguments.
2016-07-19 12:51:34 -07:00
Jakob Stoklund Olesen
39d3a8e3d7 Implement separate data flow graph module.
The DFG keeps track of instruction definitions, values, and EBBs.

Store the primary definition of each instruction: Opcode and operands.
Track SSA values as either the result of an instruction or EBB arguments.
2016-07-19 12:51:34 -07:00
Jakob Stoklund Olesen
78ce51e166 Don't require Clone + Default for EntityMap values.
There are two kinds of entity maps:

- A primary map is used to allocate entity references and store the primary
  entity data. This map only grows when adding new entities with 'push'.

- A secondary map contains additional information about entities in a primary
  map. This map always grows with 'ensure', making default entries for any
  unknown primary entities.

Only require the 'Default + Clone' traits for values stored in a secondary map.

Also remove the 'grow automatically' feature of the IndexMut implementation.
This means that clients need to call 'ensure' whenever using a potentially
unknown entity reference.

The 'grow automatically' feature could not be implemented for the Index trait,
and it seems unfortunate to have different semantics for Index and IndexMut.
2016-07-19 09:53:55 -07:00
Jakob Stoklund Olesen
d64e7fb576 Don't require Clone + Default for EntityMap values.
There are two kinds of entity maps:

- A primary map is used to allocate entity references and store the primary
  entity data. This map only grows when adding new entities with 'push'.

- A secondary map contains additional information about entities in a primary
  map. This map always grows with 'ensure', making default entries for any
  unknown primary entities.

Only require the 'Default + Clone' traits for values stored in a secondary map.

Also remove the 'grow automatically' feature of the IndexMut implementation.
This means that clients need to call 'ensure' whenever using a potentially
unknown entity reference.

The 'grow automatically' feature could not be implemented for the Index trait,
and it seems unfortunate to have different semantics for Index and IndexMut.
2016-07-19 09:53:55 -07:00
Morgan Phillips
79211cb8a6 Fix formatting 2016-07-18 20:30:33 -07:00
Morgan Phillips
f63d7941ed Fix formatting 2016-07-18 20:30:33 -07:00
Jakob Stoklund Olesen
652ebbdc27 Use EBB layout order almost everywhere.
The ebbs_numerically() function was a workaround for the unimplemented EBB layout
order.
2016-07-18 18:52:35 -07:00
Jakob Stoklund Olesen
8c58fe4631 Use EBB layout order almost everywhere.
The ebbs_numerically() function was a workaround for the unimplemented EBB layout
order.
2016-07-18 18:52:35 -07:00
Jakob Stoklund Olesen
4f7c624ba6 Implement IntoIterator for Layout. 2016-07-18 18:47:42 -07:00
Jakob Stoklund Olesen
4ee2ab5042 Implement IntoIterator for Layout. 2016-07-18 18:47:42 -07:00
Jakob Stoklund Olesen
d73c2c9dc0 Replace inst_order with Layout in Function.
The Layout also handles EBB layout, so new append_ebb calls are necessary.

- Rewrite callers to use the public data member 'layout'.
- Implement Debug for Function in terms of the write module to avoid deriving
  it.
2016-07-18 18:23:32 -07:00
Jakob Stoklund Olesen
e926674b4e Replace inst_order with Layout in Function.
The Layout also handles EBB layout, so new append_ebb calls are necessary.

- Rewrite callers to use the public data member 'layout'.
- Implement Debug for Function in terms of the write module to avoid deriving
  it.
2016-07-18 18:23:32 -07:00
Jakob Stoklund Olesen
0ef0937016 More layout tests and bugfixes.
Fix bugs in append methods. Linked lists are hard.
2016-07-18 18:09:31 -07:00
Jakob Stoklund Olesen
2f74efd5fc More layout tests and bugfixes.
Fix bugs in append methods. Linked lists are hard.
2016-07-18 18:09:31 -07:00
Jakob Stoklund Olesen
bd2945ab5e Implement instruction order.
Each EBB has a linked list of instructions in layout order.
2016-07-18 15:05:26 -07:00
Jakob Stoklund Olesen
21c2474d4d Implement instruction order.
Each EBB has a linked list of instructions in layout order.
2016-07-18 15:05:26 -07:00
Morgan Phillips
b8fbd0668c Merge pull request #9 from mrrrgn/testutils
Move test utility functions to their own module
2016-07-18 14:42:58 -07:00
Morgan Phillips
0bee6b3c96 Merge pull request #9 from mrrrgn/testutils
Move test utility functions to their own module
2016-07-18 14:42:58 -07:00
Jakob Stoklund Olesen
0d924c67d0 Add Layout::ebbs() and the corresponding iterator.
Implement some tests, fix bugs in is_ebb_inserted().
2016-07-18 14:36:27 -07:00
Jakob Stoklund Olesen
a641bdb1f2 Add Layout::ebbs() and the corresponding iterator.
Implement some tests, fix bugs in is_ebb_inserted().
2016-07-18 14:36:27 -07:00
Morgan Phillips
ea3d2f0bbd Move test utility functions to their own module 2016-07-18 14:28:00 -07:00
Morgan Phillips
28c1eda4f6 Move test utility functions to their own module 2016-07-18 14:28:00 -07:00
Jakob Stoklund Olesen
c76ba3a7f6 Add an EntityRef::wrap() method.
This is the opposite of unwrap(). It converts the ad-hoc null references like
NO_EBB and NO_INST into the more standard Option<Ebb> type which unfortunately
takes twice as much space in data structures.
2016-07-18 14:27:12 -07:00
Jakob Stoklund Olesen
b9975f77af Add an EntityRef::wrap() method.
This is the opposite of unwrap(). It converts the ad-hoc null references like
NO_EBB and NO_INST into the more standard Option<Ebb> type which unfortunately
takes twice as much space in data structures.
2016-07-18 14:27:12 -07:00
Morgan Phillips
32f40168b5 Remove extra newline 2016-07-16 15:33:30 -07:00
Morgan Phillips
8bbc75e39f Remove extra newline 2016-07-16 15:33:30 -07:00
Jakob Stoklund Olesen
d3ed162bac Begin a layout module.
The Layout data structure will keep track of the order of EBBs and their
instructions.

WIP.
2016-07-15 16:12:31 -07:00
Jakob Stoklund Olesen
5c15dcdebb Begin a layout module.
The Layout data structure will keep track of the order of EBBs and their
instructions.

WIP.
2016-07-15 16:12:31 -07:00
Jakob Stoklund Olesen
4358a4d96e Implement EntityRef for most of the entities module.
The only exception is Value which has two dimensions.
2016-07-15 16:03:14 -07:00
Jakob Stoklund Olesen
99464bc29d Implement EntityRef for most of the entities module.
The only exception is Value which has two dimensions.
2016-07-15 16:03:14 -07:00
Jakob Stoklund Olesen
e874393419 Add an entity_map module.
This supports the pattern of creating structs wrapping a u32 and using them as
indexes into a vector of entities. These entity references should implement the
EntityRef trait.

The EntityMap is a generic map from an EntityRef to some value type. It expects
densely indexed entities and uses a Vec to represent the mapping compactly.
2016-07-15 15:17:11 -07:00
Jakob Stoklund Olesen
191c607bf9 Add an entity_map module.
This supports the pattern of creating structs wrapping a u32 and using them as
indexes into a vector of entities. These entity references should implement the
EntityRef trait.

The EntityMap is a generic map from an EntityRef to some value type. It expects
densely indexed entities and uses a Vec to represent the mapping compactly.
2016-07-15 15:17:11 -07:00
Morgan Phillips
c69ebe6a46 Merge pull request #8 from mrrrgn/graphviz
Graphviz
2016-07-14 13:44:57 -07:00
Morgan Phillips
2901198815 Merge pull request #8 from mrrrgn/graphviz
Graphviz
2016-07-14 13:44:57 -07:00
Morgan Phillips
41d4cdba46 Add print-cfg tests 2016-07-14 13:43:11 -07:00