loop.hpp File Reference

interface of a loop More...

#include "custom_map.hpp"
#include "custom_set.hpp"
#include "graph.hpp"
#include "panda_types.hpp"
#include "refcount.hpp"
#include <cstddef>
#include <list>
#include <utility>

Include dependency graph for loop.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
class	Loop

Macros
Constants identifying the type of the loops
#define	SINGLE_EXIT_LOOP   1
	loop with single exit More...
#define	UNKNOWN_LOOP   2
	unknown loop More...
#define	WHILE_LOOP   4
	while or for loop More...
#define	FOR_LOOP   8
	for loop More...
#define	DOALL_LOOP   16
	parallelizable for loop More...
#define	DO_WHILE_LOOP   32
	do while loop More...
#define	COUNTABLE_LOOP   64
	countable loop More...
#define	PIPELINABLE_LOOP   128
	pipelinable loop More...

Typedefs
using	LoopRef = refcount< Loop >
	refcount definition of the class More...

Functions
	REF_FORWARD_DECL (BBGraph)
	CONSTREF_FORWARD_DECL (Loop)
	REF_FORWARD_DECL (Loop)
	REF_FORWARD_DECL (Loops)
	CONSTREF_FORWARD_DECL (OpGraph)
	REF_FORWARD_DECL (tree_node)

Detailed Description

interface of a loop

A loop is a strongly connected component in a CFG. We use Tarjan algorithm to build a loop forest (see loops.h). Loop represents a single loop. A loop is composed by a set of nodes and arcs which belong to the CFG. Some of the nodes in a loop are special and have been given a name. Some nodes outside the loop are also somehow related to loops and have a special name. Here we introduce the naming conventions we will be using.

---

| PreHeader |

| |-----------—>| | V | --------------------— | | Header | | --------------------— | | | | | V | --------------------— | | Any CFG allowed | | --------------------— | | | | | V | --------------------— | | Exit | | --------------------— | | -------------—|

V

| Landing pad |

This example shows an example of a loop, but it is not the most general case. The example has the following properties:

1) it is bottom tested (the exit condition is evaluated at the end of the loop, which means the loop is do-while) 2) it is reducible (single entry point) 3) has a single pre header (for reducible loops it is always possible to change the CFG to meet this condition) 4) has a single exit 5) has a single landing pad 6) has a single back edge (for a definition of back edge see for example Tarjan)

In general a loop can be much more complicated, having multiple entries (in C this can be achieved using gotos), mutiple exits, landing pads and back edges.

In our Loop representation a loop has a header (and only one!) if and only if the loop is reducible. If the loop is not reducible then there's no header info. Exits are kept in a list and landing pads as well. An interesting case is when we have N landing pads and N-1 landing pads have a single successor being the Nth landing pad. This case is generate by break statements in C/C++. For this reason a Loop has a special property to signal this case.

Author

Marco Garatti m.gar.nosp@m.atti.nosp@m.@gmai.nosp@m.l.co.nosp@m.m

Marco Lattuada lattu.nosp@m.ada@.nosp@m.elet..nosp@m.poli.nosp@m.mi.it $Revision$ $Date$ Last modified by $Author$

Definition in file loop.hpp.

Macro Definition Documentation

COUNTABLE_LOOP

#define COUNTABLE_LOOP   64

countable loop

Definition at line 138 of file loop.hpp.

Referenced by Vectorize::ClassifyLoop(), LoopsAnalysisBambu::InternalExec(), and Loops::WriteDot().

DO_WHILE_LOOP

#define DO_WHILE_LOOP   32

do while loop

Definition at line 135 of file loop.hpp.

Referenced by LoopsAnalysisBambu::InternalExec(), and Loops::WriteDot().

DOALL_LOOP

#define DOALL_LOOP   16

parallelizable for loop

Definition at line 132 of file loop.hpp.

Referenced by pragma_manager::CheckAddOmpFor(), pragma_manager::CheckAddOmpSimd(), Vectorize::ClassifyLoop(), Vectorize::HasToBeExecuted(), ExtractOmpFor::InternalExec(), Loops::WriteDot(), EdgeCWriter::writeRoutineInstructions_rec(), and CWriter::writeRoutineInstructions_rec().

FOR_LOOP

#define FOR_LOOP   8

for loop

Definition at line 129 of file loop.hpp.

Referenced by Loops::WriteDot().

PIPELINABLE_LOOP

#define PIPELINABLE_LOOP   128

pipelinable loop

Definition at line 141 of file loop.hpp.

Referenced by LoopsAnalysisBambu::InternalExec(), and Loops::WriteDot().

SINGLE_EXIT_LOOP

#define SINGLE_EXIT_LOOP   1

loop with single exit

Definition at line 120 of file loop.hpp.

Referenced by LoopsAnalysisBambu::InternalExec(), and Loops::WriteDot().

UNKNOWN_LOOP

#define UNKNOWN_LOOP   2

unknown loop

Definition at line 123 of file loop.hpp.

Referenced by LoopsAnalysisBambu::InternalExec(), and Loops::WriteDot().

WHILE_LOOP

#define WHILE_LOOP   4

while or for loop

Definition at line 126 of file loop.hpp.

Referenced by LoopsAnalysisBambu::InternalExec(), and Loops::WriteDot().

Typedef Documentation

LoopRef

using LoopRef = refcount<Loop>

refcount definition of the class

Definition at line 406 of file loop.hpp.

Function Documentation

CONSTREF_FORWARD_DECL() [1/2]

CONSTREF_FORWARD_DECL

(

Loop

)

CONSTREF_FORWARD_DECL() [2/2]

CONSTREF_FORWARD_DECL

(

OpGraph

)

REF_FORWARD_DECL() [1/4]

REF_FORWARD_DECL

(

BBGraph

)

REF_FORWARD_DECL() [2/4]

REF_FORWARD_DECL

(

Loop

)

REF_FORWARD_DECL() [3/4]

REF_FORWARD_DECL

(

Loops

)

REF_FORWARD_DECL() [4/4]

REF_FORWARD_DECL

(

tree_node

)