Region based SCoP detection

An approach to rewrite the Static Control Parts (SCoPs) detection of the Graphtie to use the program structure tree.

Current state

The central method in the SCoP detection is at the moment build_scops(). It does several things:

  1. build_scops_1()
  2. create_sese_edges()
  3. limit_scops()

So what are these steps:

build_scops_1():

This function together with "scopdet_basic_block_info" build the heart of the SCoP detection. They do several things at a time:

All this works on unstructured control flow, is well tested and works. However it is too hard to understand and not well structured. (=> Tobi's fault) Furthermore it is difficult to extend.

create_sese_edges():

As the previous pass can detect SCoPs that are refined regions, it is necessary to insert merge basic blocks to create a single entry single exit edge for every detected SCoP as this simplifies code generation.The merge basic blocks are inserted in this function.

limit_scop():

It only allows regions that are surrounded by a single loop. This is necessary as the scalar evolution does not yet support regions that do not have a surrounding loop. At the moment it is hard to remove as it hides some bugs in the code generation.

New approach:

A better approach would be to separate the steps of the SCoP detection.

  1. Build the Regions tree
  2. Check which regions could be valid SCoPs
  3. Select the maximal Region that is a valid SCoP

Build the regions tree

There are several approaches possible. First of all there is the current patchset Sebastian posted on the mailing list. It works however at the moment we can find all refined regions. It should be checked if it will give us a refined region tree by inserting the right basic blocks beforehand. Another approach is to implement an algorithm as described in the RPST work.

Check which regions are valid SCoPs

Here the harmful_stmt_in_bb() function can be reused. However it has to take different parameters. Instead of harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb) it should take harmful_stmt_in_bb (region r, basic_block bb). This change will need some work on the support of scalar evolution on regions.

Furthermore it has be checked that the regions just contain structured control flow.

Find the maximal regions

This is easy as long as we work with canonical regions. However as soon as a maximal canonical region is found is should be checked canonical regions that are right behind each other can be combined to a larger region.

Future Extensions:

The intent is to partition the CFG into minimal SESE regions, or black boxes, that internally cannot be represented in the polyhedral model: i.e. they contain non linear conditions, switches and loops, etc., but at a macro level the dependences between these black boxes are regular enough to be represented in the polyhedral model.

None: Graphite/SCoP_detection_on_sese_regions (last edited 2010-04-28 15:44:09 by TobiasGrosser)