Polaris: DDgraph.h Source File

DDgraph.h Go to the documentation of this file. #ifndef _DD_GRAPH_H #define _DD_GRAPH_H /// /// /// /// \class DDgraph /// \brief a semantic interface to the Data Dependence Graph. /// \defgroup Polaris /// \ingroup Polaris /// Base /// \see DDgraph.h /// \see DDgraph.h /// /// \endcode /// \section Overview Overview /// The DDgraph provides the user with information about the data /// dependences contained in a program. /// /// \endcode /// \section Description Description /// The DDgraph provides the user with information about the data /// dependences contained in a program. /// /// \endcode /// \section Caveats Caveats /// A paragraph describing unusual features of the class. /// This paragraph may be omitted. /// #define _DDG_TEST /// #ifdef _DDG_TEST class DDgraphTester; #endif #ifdef POLARIS_GNU_PRAGMAS #pragma interface #endif #include <assert.h> #include "Symbol/Symbol.h" #include "Statement/Statement.h" #include "StmtList.h" #include "Collection/List.h" #include "Collection/RefList.h" #include "Collection/Iterator.h" #include "Collection/Mutator.h" #include "Expression/Expression.h" #include "Expression/ArrayRefExpr.h" #include "Expression/IDExpr.h" #include "macros.h" #include "ArcSpec.h" class Program; class DDgraph; class DDiterator; typedef signed char Binary_flag; ///< Used for flags with on/off as its values enum DDtests_Seq { ///< Specify the sequence of the dd-tests to be used ///< Currently the sequence is fixed, and the only option uesr might ///< choose is what tests are included and omitted in this fixed sequence _None, _GCD_Only, ///< Constant_test included here _Banerjee_Only, _Omega_Only, _GCD_Banerjee, _Banerjee_Omega, _GCD_Omega, _All }; enum DDI_INIT_TYPE { ///< DDiterator object is initialized ///< tells how 'from/to'-statement of _STMTS, _EXPR }; enum In_Out_refs { ///< Used only in DDiterator _IN_REFS, _OUT_REFS }; enum First_Last { ///< Used in compute_dvf_n_arc() _FIRST, _LAST }; ///< An ElementDV object corresponds to a direction whose value is one of ///< <,>,=,<=,=>,<>,* and a delimiter '000'. List<ElementDV> is a drection ///< vector and is included in a DVfield object. Through ElementDV, we can ///< do elemental operations querying/updating one direction element of a ///< direction vector. For more general operations for a direction vector ///< such as expanding/shrinking/ a DV itself by adding/deleting its ///< elements, we may use the member functions provided in a DVfield object. class ElementDV : public Listable { private: DIREC_TYPE _direction; DDIST_TYPE _min_distance; ///< lower bound on distance DDIST_TYPE _max_distance; ///< upper bound on distance Boolean _distance_valid; ///< distance valid bit public: inline ElementDV(DIREC_TYPE direc); inline ElementDV(const ElementDV & other); inline ElementDV(DIREC_TYPE direc, DDIST_TYPE const_distance); inline ElementDV(DIREC_TYPE direc, DDIST_TYPE min, DDIST_TYPE max); ~ElementDV(); inline DIREC_TYPE direction() const; inline void direction(DIREC_TYPE new_direc); ///< Query or Update a direction ///< Query or Update a distance inline Boolean is_distance_valid (); ///< check valid inline void make_distance_valid (); ///< make valid inline Boolean is_distance_constant (); ///< check constant distance ///< query and update distance components; inline DDIST_TYPE distance (); inline void distance(DDIST_TYPE new_distance); inline DDIST_TYPE min_distance (); inline void min_distance (DDIST_TYPE new_min_distance); inline DDIST_TYPE max_distance (); inline void max_distance (DDIST_TYPE new_max_distance); virtual Listable *listable_clone() const; ///< Duplicate copy of this object virtual void print(ostream & o) const; }; ///< DVfield is a basic unit of data dependence information between two ///< expressions and is built by a DDiterator object. The information it ///< keeps inside it is as follows; ///< one direction vector for the dependence relation, ///< dependency decision(assumed/proved), ///< dependence type(flow/anti/input/output), ///< pointers to the expressions & statements related to the dependency. class DVfield : public Listable { private: #ifdef _DDG_TEST friend class DDgraphTester; #endif friend class DDgraph; int _references; ///< Number of DDiterators currently pointing to this DVfield. Binary_flag _valid; ///< If this field is off, this DVfield is no longer valid. ///< The last iterator which leaves this node will dispose this. DEP_DECISION _dep_decided; DEP_TYPE _dep_type; const Expression & _from_expr; const Expression & _to_expr; ///< There is dependency arc from _from_expr to _to_expr const Statement & _from_stmt; const Statement & _to_stmt; ///< _from/to_expr belong to _from/to_stmt, respectively Expression *_label; List<ElementDV>_dv; ///< List of dependence directions inline int references_inc(); inline int references_dec(); ///< increase/decrease the reference count by one and return ///< the new count inline void valid_on(); inline void valid_off(); ///< make this DVfield valid/invalid public: inline DVfield(DEP_DECISION dep_decided, DEP_TYPE dep_type, const Statement & from_stmt, const Expression & from_expr, const Statement & to_stmt, const Expression & to_expr); inline DVfield(const DVfield & other); ~DVfield(); inline DEP_DECISION dep_decided(); inline void dep_decided(DEP_DECISION new_ddecided); ///< Query or update dep_decided/assumed dependency flag in DVfield inline DEP_TYPE dep_type(); inline void dep_type(DEP_TYPE new_dtype); ///< Query or update dependence type in DVfield inline const Expression & from_expr(); inline const Expression & to_expr(); inline const Statement & from_stmt(); inline const Statement & to_stmt(); ///< Get the information about what expressions and statements ///< are involoved in this dependency relation ///< There are two ways to build a direction vector as follows; ///< -> adding one element by one element: dv() ///< -> copying everything from another: dv(List<ElementDV>&) inline List<ElementDV>&dv(); ///< Get a reference of the direction vector. ///< Using this reference, a new DV can be built or reorganized. ///< First get this reference, and insert or delete some of elements ///< of this DV by using the operations provided in class List<>. inline void dv(List<ElementDV>&new_dv); ///< copy constructor - another way to build a DV. ///< If the DV is only for this DVfield, we recommend to use ///< the way described above rather than this copy constructor. Expression *label() { return _label; } void setLabel(Expression *label) { _label = label; } virtual Listable *listable_clone() const; ///< Duplicate copy of this object virtual void print(ostream & o) const ; }; ///< A list of these ActiveArc objects are directly managed by an DDgraph ///< object. This is an uncompacted version of an arc which is embedded ///< in a ProgramUint. Most of the fields in this object are based on the ///< arc. When the first visitor(DDiterator) arrives some arc, the 'active' ///< field is made to be turned on and most of the values in the arc are ///< copied into the DDgraph creating a new ActiveArc object. Every operation ///< on arc is actually performed on this object through the DDgraph by each ///< DDiterator. When all of DDiterators leave this object, the most updated ///< data in this will be copied back into the corresponing arc in the ///< ProgramUnit. Currently every member and operation is accessed and managed ///< by DDgraph only. class ActiveArc : public Listable { private: #ifdef _DDG_TEST friend class DDgraphTester; #endif friend class DDgraph; int _references; ///< Number of DDiterators pointing this active arc ///< (cf: _references in DVfield object) Arc_type *_this_arc; Arc_type *_prev_arc; Arc_type *_next_arc; ///< pointing to the this/previous/next arcs in the compacted form, ///< respectively. _this_arc is the current arc whose data is ///< originally copied into this ActiveArc object. const Expression & _source_expr; const Expression & _target_expr; ///< Dependency is described in terms of two expressions, source and ///< target. Dependence direction is from the source to the target. ///< For instance, if the direction is reverse(_REVERSE), ///< then that implies the source is dependent on the target. ///< _source_expr is the current expression which points to the current ///< arc. const Statement & _source_stmt; const Statement & _target_stmt; ///< _source_stmt has _source_expr and _target_stmt does _target_expr. ///< _source_stmt is the current statement. List<DVfield>*_original_dv_fields; ///< An exact copy of the original DVfields stored in the arc List<DVfield>_working_dv_fields; ///< Initially, the same copy with the original list, ///< _original_dv_fields. Unlike it, the contents of this list are ///< changed by DDiterators or users, as time goes by. When this ///< ActiveArc is decativated(destructed), this list is compared with ///< the original list. If they are diffrent, the working list will be ///< overwritten onto the corresponding arc in a ProgramUnit. Especially, ///< if their size are also diffrent, the arc will be deallocated and a ///< new space will be allocated to accomodate the working list. ///< CC 06/15/98 Expression *_label; ///< denotes the number of references accessed between source and dest. ///< used for the stack algorithm ///< CC end public: ///< Initialized with the address of the original arc and its size in ///< terms of the number of bits, also initializing the other members ///< with proper values inline ActiveArc(DDgraph & ddg, Arc_type * original_arc, Arc_type * prev_of_origin, Arc_type * next_of_origin, const Statement & src_stmt, const Expression & src_expr); inline ActiveArc(const ActiveArc & other); ~ActiveArc(); virtual void print(ostream & o) const; virtual Listable *listable_clone() const; ///< Duplicate copy of this object ///< CC 06/15/98 Expression *label() { return _label; } void setLabel(Expression *label) { _label = label; } ///< CC end }; ///< Interface for access to the elements in Data Dependence(DD) graph. ///< Some of operations are allowed only to DDiterator objects and the ///< others are allowed to general users, such as adding some dependency ///< information into DDgraph. DDgraph can exclusively access all the ///< private elements of DVfield and ActiveArc, and the original arcs ///< itself(defined as a private member of Expression and DDgraph is ///< its friend). class DDgraph { private: #ifdef _DDG_TEST friend class DDgraphTester; #endif friend class ActiveArc; friend class DDiterator; ///< to use the private member functions const int _ptr_size; ///< Size of a pointer type in bits const int _tgt_expr_offset; const int _label_offset; const int _next_arc_offset; const int _data_field_offset; ///< Offsets for three pointers stored in an arc StmtList & _stmts; ///< Statement list of this ProgramUnit inline Arc_type *arcs_ptr(const Expression & src_expr); ///< Return the pointer to the original arc ///< Return NULL if src_expr.op is not either ID nor Array Reference List<ActiveArc>_active_arcs; ///< Initially, an empty list inline void _clear_arc(Arc_type * arc, int bytes); inline Binary_flag is_active(Arc_type * arc); inline void activate(Arc_type * arc); inline void deactivate(Arc_type * arc); ///< query/activate/deactivate the arc by accessing the active flag ///< stored in arc_field where each arc is represented by a consecutive ///< series of Arc_type variables and 'arc_field' is one of them inline Statement *target_stmt(Arc_type * arc) const; inline Expression *target_expr(Arc_type * arc) const; inline Expression *label_expr(Arc_type * arc) const; inline Arc_type *next_arc(Arc_type * arc) const; inline Arc_type *data_field(Arc_type * arc) const; ///< Return the pointers to the appropriate type stored in 'arc' inline void store_target_stmt(Arc_type * arc, const Statement & stmt); inline void store_target_expr(Arc_type * arc, const Expression & expr); inline void store_label_expr(Arc_type * arc, const Expression & expr); inline void store_next_arc(Arc_type * arc, Arc_type * next); ///< Store the pointers to the appropriate type into 'arc' Binary_flag is_new_dvfield(Arc_type * &arc_field, int &position); DEP_DECISION dep_decision(Arc_type * &arc_field, int &position); DEP_DIREC dep_direction(Arc_type * &arc_field, int &position); DEP_TYPE dep_type(Arc_type * &arc_field, int &position); DIREC_TYPE direction(Arc_type * &arc_field, int &position); DDIST_TYPE min_distance(Arc_type * &arc_field, int &position); DDIST_TYPE max_distance(Arc_type * &arc_field, int &position); ///< 'arc_field' is one Arc_type variable which contains the part of the ///< information of DV fields such as dependence decision, dependence ///< direction, and so on. The field to be extracted from 'arc_field' ///< starts from ('position'-1)th bit. The value of 'position' will be ///< changed to the beginning position of the next field after the ///< current field is extracted and returned. Since sizeof(Arc_type) ///< is currently a byte, 'position' normally ranges from 0 to 7. ///< The next 'position' is normally 'position' + length(current field), ///< but if sizeof(Arc_type) < the next 'position', then the next ///< 'position' become position' + length(current field) - sizeof(Arc_type) ///< and arc_field is moved to the next one by arc_field++. So, arc_field ///< and position are always supposed to point to the beginning of the next ///< field when the function is returned. inline DEP_DIREC test_dep_direction(Arc_type * arc_field, int offset); ///< Unlike the above methods, there is no side effect and 'offset' can ///< be greater then A_BYTE. 'offset' is counted from the beginning of ///< 'arc_field'. void mark_new_dvfield(Arc_type * &arc_field, int &position); void mark_arc_end(Arc_type * &arc_field, int &position); void store_dep_decision(Arc_type * &arc_field, int &position, DEP_DECISION ddeci); void store_dep_direction(Arc_type * &arc_field, int &position, DEP_DIREC ddirec); void store_dep_type(Arc_type * &arc_field, int &position, DEP_TYPE deptype); void store_direction(Arc_type * &arc_field, int &position, DIREC_TYPE direct); void store_min_distance(Arc_type * &arc_field, int &position, DDIST_TYPE min_dist); void store_max_distance(Arc_type * &arc_field, int &position, DDIST_TYPE min_dist); void store_const_distance(Arc_type * &arc_field, int &position, DDIST_TYPE const_dist); ///< Store each field data into the Arc_type variable by appending it ///< at the end of the valid data so far stored. ///< arc_field must be initially cleared before it is filled with the ///< fields. inline Arc_type _test_1bit_field(Arc_type * arc_field, int offset); ///< Test and return dep. direction which is located at the 'offset'th ///< bit from the beginning of 'arc_field'. The type of return value ///< can be Arc_type or any of its derived type, such as DEP_TYPE. NO ///< Side effect. inline void _skip_this_dvfield(Arc_type * &arc_field, int &position); ///< When this is called, pair(arc_field, position) must point to the ///< dependence decision field of the current DV field. After this ///< function is performed, they are changed to point to a bit marking ///< a beginning of the next DVfield that is 1 bit before the dependence ///< decision field of the DVfield. If this DV field was the last in this ///< arc, is_new_dvfield() will return FALSE at the new position. inline int _count_this_dvfield(Arc_type * &arc_field, int &position); ///< As skipping this DVfield, count the bits and return the final ///< number. void search_active_arcs_for(DVfield * &dvf, ActiveArc * &active_arc, First_Last fl, DEP_DIREC ddirec, const Expression & from_expr, const Expression & to_expr); ///< INPUT: ddirec, src_expr, tgt_expr ///< OUTPUT: dvf, active_arc ///< ///< Search ActiveArc list for DVfield & ActiveArc with from_expr & ///< to_expr with dependence direction as ddirec, and return their ///< pointers The first of such a DVfield and an ActiveArc will be ///< returned. IF there is no such DVfield, then dvf will be NULL. ///< \note The ActiveArc with a pair 'from/to'_expr as its source and ///< target must already be in _active_arcs. void update_links_between(Arc_type * new_this, ActiveArc * active_arc); ///< Put new_this arc between prev and next arcs of active_arc:w void write_back_arc(ActiveArc * active_arc); ///< If there has any change in active_arc from the original arc, ///< write the contents of active_arc back to the orignal arc, with ///< memeory operation if necessary. ///< active_arc must have at least one DVfield at the moment. void compute_dvf_n_arc(DVfield * &dvf, ActiveArc * &active_arc, First_Last fl, const Statement & from_stmt, const Expression & from_expr, const Statement & to_stmt, const Expression & to_expr); ///< INPUT: from_stmt, from_expr, to_stmt, to_expr, fl ///< OUTPUT: dvf, active_arc ///< ///< Upon the request of DDiterator, DDgraph access the original arc and ///< check its active field. If it is active, search _active_arcs for ///< the correspondng active arc and if the active one is found then all ///< the DVfields inside it is searched again matching input arguments ///< with each of them. Depending on the value of 'fl', return the ///< first/last one which satisfy the requirement. If the original arc ///< is inactive, first search it for a matching DVfield, and if it is ///< found then create a new ActiveArc object for the arc returning the ///< pointer to the DVfield dvf in ActiveArc active_arc. If all these ///< efforts to find the right DVfield are failed, NULL will be returned ///< for the value of dvf*. DVfield *prev(DVfield * dvf, ActiveArc * active_arc); DVfield *next(DVfield * dvf, ActiveArc * active_arc); ///< Return the previous/next object of 'dvf' within the same active ///< arc. The previous/next one must have the same pairs of from/to- ///< statements and from/to-expressions with 'dvf'. If there is no ///< more such a DVfield object, NULL will be returned and simutaneously ///< check all the DV fields in the active arc to see all reference ///< values are zero(no DDiterator pointing to any DVfields in this arc). ///< If they are all zero, then update or not the original arc field ///< depending on the status of flags in ActveArc. inline void exit(DVfield * dvf, ActiveArc * active_arc); ///< When the client(DDiterator) leaves the current active arc, it must ///< report to DDgraph so that DDgraph can update the corresponding ///< active arc, esp reference count of the DVfield the client pointed ///< to last and the reference count of the active arc itself where if ///< the latter count is zero, then the active structure will be purged ///< and written back to the original arc if there are any change from ///< the original copy. No operation if dvf is NULL. void release(DVfield * dvf, ActiveArc * &active_arc); inline void hold(DVfield * dvf); ///< Handling chores which must be dealt with when we release/hold ///< DVfield. In releasing it, if the dvf is invalid and the only ///< one in active_arc, then delete the arc and make active_arc NULL. ///< In hold it, increase the reference count of the DVfield. inline void mark_dead(DVfield * dvf); ///< Invalidate dvf to mark this deleted inline Binary_flag is_alive(DVfield * dvf); ///< Return the validity of dvf inline Binary_flag is_shared(DVfield * dvf); ///< Return true if dvf is shared by more than one DDiterators inline DVfield *detach(DVfield * dvf, ActiveArc * active_arc); ///< Remove 'dvf' from 'active_arc' only inline List<DVfield>*dvfield_list(ActiveArc * active_arc); ///< Return a pointer to working_dv_filed of active_arc void initialize_this_active_arc(ActiveArc * aarc, Arc_type * arc); ///< This is called by only 'aarc' when it is created public: inline DDgraph(StmtList & stmts); inline ~DDgraph(); void add(List<DVfield>&dv_fields); ///< dv_fields is a list of DV fields where each DV field has dependency ///< information between two expressions. Instead of directly adding ///< these to DDgraph, usually turn them into a compact form and embed ///< them into the ProgramUint for the future use. But, if one of these ///< DVfields would belong to an arc which is currently active, then it ///< must be directly added to the corresponding active structure ActiveArc. }; inline DDgraph::DDgraph(StmtList & stmts) : _ptr_size(sizeof(char *) * A_BYTE), _tgt_expr_offset(sizeof(char *)), _label_offset(sizeof(char *) * 2), _next_arc_offset(sizeof(char *) * 3), _data_field_offset(sizeof(char *) * 4), _stmts(stmts) { assert(sizeof(Arc_type) == 1 && sizeof(Binary_flag) == 1); ///< p_assert("sizeof(Arc_type) & sizeof(Binary_flag) must be equal to 1 byte"); } inline DDgraph::~DDgraph() { ///< nothing to do } ///< A DDiterator object pretends to iterate over each DVfield which ///< embraces the data dependence information between two expressions ///< (See above), but it actually contains at any moment all the data ///< stored in an arc where several DVfields might be included. ///< When it has ended its iteration over all the DVfields in an arc, ///< it throws away all the information pertaing to the old arc such as ///< List<DVfield>, and moves to the next arc(if necessay, the next ///< Expression and the next Statement too) creating and organizing the ///< information for the new arc. class DDiterator { ///< DDiterator is initialized by one of the following options; ///< (2 Statement lists) -> from-statements vs. to-statements ///< (2 pairs of a Statement & an Expression) -> dependency for two ///< expressions where each lives in its partner statement, respectively ///< ///< --> A statement list must be RefList and is for randomly selected ///< statements to update/query their dependency information. private: #ifdef _DDG_TEST friend class DDgraphTester; #endif DDI_INIT_TYPE _init_from; DDI_INIT_TYPE _init_to; ///< tells how each 'from' and 'to' part of this iterator is ///< initialized. The choice is made from three selections, ///< namely, a statement list (STMTS), a pair of a statement and ///< an expression(EXPR) In_Out_refs _from_refs; In_Out_refs _to_refs; ///< Miscellaneous flags used for _iter_from/to_exprs initialization RefList<Statement> * _from_stmts; RefList<Statement> * _to_stmts; ///< If this iterator is initialized by STMTS, these keep the ///< corresponding list of statements Iterator<Statement>*_iter_from_stmts; Iterator<Statement>*_iter_to_stmts; ///< iterators for the lists of statements above Iterator<Expression>*_iter_from_exprs; Iterator<Expression>*_iter_to_exprs; ///< Keep in/out_refs() expression lists of the current statements when ///< this iterator is initialized by STMTS const Statement * _from_stmt; const Expression * _from_expr; const Statement * _to_stmt; const Expression * _to_expr; ///< If this iterator is initialized by EXPR, these keep the infomation DVfield *_current_dvf; ///< the current DV field object. ///< Must be NULL(= 0) when this iterator doen't point to anything, such ///< as when it arrives the end of the iteration space. ActiveArc *_active_arc; ///< in which _current_dvf lives DDgraph & _ddgraph; ///< This is the only interface through which a DDiterator can access ///< DVfields inside a data dependence graph. DDiterator can read or ///< call any private members but not modify them directly. ///< We are supposed to have a unique _ddgraph pointer per ProgramUni. void _next_in_STMTS_n_STMTS(); void _next_in_STMTS_n_EXPR(); void _next_in_EXPR_n_STMTS(); void _prev_in_STMTS_n_STMTS(); void _prev_in_STMTS_n_EXPR(); void _prev_in_EXPR_n_STMTS(); ///< Compute previous/next DVfield of the current position in the ///< iteration space. This choice of the computation is distingushed ///< by the method of the initialization, such as (from == STMTS, ///< to == STMTS). public: DDiterator(RefList<Statement> * from_stmts, RefList<Statement> * to_stmts, DDgraph & ddgraph); ///< The ownership of both RefLists is transfered to DDiterator. ///< That means DDiterator will delete these lists later(Note: since ///< they are RefLists, their elements<each Statement> won't be deleted, ///< but the lists itself will be dissolved). inline DDiterator(const Statement & from_stmt, const Expression & from_expr, const Statement & to_stmt, const Expression & to_expr, DDgraph & ddgraph); DDiterator(RefList<Statement> * from_stmts, const Statement & to_stmt, const Expression & to_expr, DDgraph & ddgraph); DDiterator(const Statement & from_stmt, const Expression & from_expr, RefList<Statement> * to_stmts, DDgraph & ddgraph); DDiterator(const DDiterator & other); ///< This method copies the entire state (including current arc) ///< of the iterator. If you don't like this, then immediately follow ///< this constructor with a call to reset() inline ~DDiterator(); ///< Release the current DVfield on exiting inline Boolean valid(); inline Boolean end(); ///< Used to check if there are more Nodes to iterate on. ///< If yes, then valid() returns TRUE, else FALSE. ///< end() is equivalent to NOT valid(). inline DVfield & current(); ///< Return a reference to the current DV field of the current arc. ///< If there is no current, this results in an error. ///< This is always suppposed to return VALID node, since every invalid ///< node will be automatically skipped. ///< CC 06/15/98 ActiveArc *current_arc() { return _active_arc; } ///< CC end inline Boolean current_valid(); inline Boolean current_invalid(); ///< tells whether or not this node is valid. ///< Even though DDiterator guarantees to return valid node in response ///< to current(), there is still chance for the current node to become ///< invalid by grab() called by the other iterator which shares it. ///< Since accessing any members in invalid object causes an error, ///< checking for validity of the current might be necessary for safety ///< reason. inline DVfield *grab(); ///< Grab the current element after deleting or invalidating it from the ///< list inline void modify(DVfield * other); ///< Subsititude new_dv_field for the DVfield currently pointed by ///< iterator inline void del(); ///< Delete the current DVfield. ///< If this DVfield is only one left in the current arc, ///< the arc would also be deleted(invalidated or deallocated). ///< Move operations: reset, set_to_last, next, prev, ++, -- ///< -> When an iterator leaves one arc for another, the list DVfields ///< will be overwritten to the old arc in a compacted form subject ///< to its modification in the arc. no modification, no overwriting. void reset(); void set_to_last(); ///< Move the current arc position in the iteration space ///< to the beginning or to the last. ///< Moving to the last might be useful if you need to iterator ///< backwards ///< void prev(); void operator-- (); ///< Go to the previous valid arc. ///< void next(); void operator++ (); ///< Go to the next valid arc. }; ///< /////// inline codes inline ElementDV::ElementDV(DIREC_TYPE direc) { _direction = direc; _distance_valid = False; _min_distance = INV_DDIST; _max_distance = INV_DDIST; } inline ElementDV::ElementDV(DIREC_TYPE direc, DDIST_TYPE const_distance) { _direction = direc; _min_distance = const_distance; _max_distance = const_distance; _distance_valid = True; } inline ElementDV::ElementDV(DIREC_TYPE direc, DDIST_TYPE min, DDIST_TYPE max) { _direction = direc; _min_distance = min; _max_distance = max; _distance_valid = True; } inline ElementDV::ElementDV(const ElementDV & other) { _direction = other._direction; _min_distance = other._min_distance; _max_distance = other._max_distance; _distance_valid = other._distance_valid; } inline DIREC_TYPE ElementDV::direction() const { return _direction; } inline void ElementDV::direction(DIREC_TYPE new_direc) { _direction = new_direc; } inline Boolean ElementDV::is_distance_valid () { ///< return(_distance_valid); return (_min_distance != INV_DDIST && _max_distance != INV_DDIST); } inline void ElementDV::make_distance_valid () { _distance_valid = True; } inline Boolean ElementDV::is_distance_constant () { return (_min_distance == _max_distance); } inline DDIST_TYPE ElementDV::distance () { ///< will not check to see if actually constant return(_min_distance); } inline void ElementDV::distance(DDIST_TYPE new_distance) { _min_distance = new_distance; _max_distance = new_distance; _distance_valid = True; } inline DDIST_TYPE ElementDV::min_distance () { return(_min_distance); } inline void ElementDV::min_distance (DDIST_TYPE new_min_distance) { _min_distance = new_min_distance; _distance_valid = True; } inline DDIST_TYPE ElementDV::max_distance () { return(_max_distance); } inline void ElementDV::max_distance (DDIST_TYPE new_max_distance) { _max_distance = new_max_distance; _distance_valid = True; } inline DVfield::DVfield(DEP_DECISION dep_decided, DEP_TYPE dep_type, const Statement & from_stmt, const Expression & from_expr, const Statement & to_stmt, const Expression & to_expr) : _from_expr(from_expr), _to_expr(to_expr), _from_stmt(from_stmt), _to_stmt(to_stmt), _label(NULL) { _dep_decided = dep_decided; _dep_type = dep_type; _valid = 1; _references = 0; } inline DVfield::DVfield(const DVfield & other) : _from_expr(other._from_expr), _to_expr(other._to_expr), _from_stmt(other._from_stmt), _to_stmt(other._to_stmt) { _dep_decided = other._dep_decided; _dep_type = other._dep_type; _valid = other._valid; _references = other._references; if(other._label != NULL) _label = other._label->clone(); else _label = NULL; } inline int DVfield::references_inc() { return ++_references; } inline int DVfield::references_dec() { return --_references; } inline void DVfield::valid_on() { _valid = 1; } inline void DVfield::valid_off() { _valid = 0; } inline DEP_DECISION DVfield::dep_decided() { return _dep_decided; } inline void DVfield::dep_decided(DEP_DECISION new_ddecided) { _dep_decided = new_ddecided; } inline DEP_TYPE DVfield::dep_type() { return _dep_type; } inline void DVfield::dep_type(DEP_TYPE new_dtype) { _dep_type = new_dtype; } inline const Expression & DVfield::from_expr() { return _from_expr; } inline const Expression & DVfield::to_expr() { return _to_expr; } inline const Statement & DVfield::from_stmt() { return _from_stmt; } inline const Statement & DVfield::to_stmt() { return _to_stmt; } inline List<ElementDV> & DVfield::dv() { return _dv; } inline void DVfield::dv(List<ElementDV>&new_dv) { Iterator<ElementDV> iter = new_dv; for (; iter.valid(); ++iter) _dv.ins_last(new ElementDV(iter.current())); } inline ActiveArc::ActiveArc(DDgraph & ddg, Arc_type * arc, Arc_type * prev, Arc_type * next, const Statement & src_stmt, const Expression & src_expr) : _this_arc(arc), _prev_arc(prev), _next_arc(next), _source_expr(src_expr), _target_expr(*ddg.target_expr(arc)), _source_stmt(src_stmt), _target_stmt(*ddg.target_stmt(arc)) { ddg.initialize_this_active_arc(this, arc); ///< CC 06/15/98 _label = ddg.label_expr(arc); ///< CC end } inline ActiveArc::ActiveArc(const ActiveArc & other) : _source_expr(other._source_expr), _target_expr(other._target_expr), _source_stmt(other._source_stmt), _target_stmt(other._target_stmt) { _this_arc = other._this_arc; _prev_arc = other._prev_arc; _next_arc = other._next_arc; ///< CC 06/15/98 _label = (other._label != NULL) ? other._label->clone() : NULL; ///< CC end } inline Arc_type * DDgraph::arcs_ptr(const Expression & src_expr) { switch (src_expr.op()) { case ID_OP: return ((IDExpr &) src_expr)._arcs; case ARRAY_REF_OP: return ((ArrayRefExpr &) src_expr)._arcs; default: return NULL; ///< Only ID & ArrayRef Expression concerned } } inline void DDgraph::_clear_arc(Arc_type * arc, int bytes) { while (bytes-- > 0) arc[bytes] = '\0'; } inline Binary_flag DDgraph::is_active(Arc_type * arc) { return (Binary_flag) (*(arc + _data_field_offset) & ARC_ACTIVE); } inline void DDgraph::activate(Arc_type * arc) { *(arc + _data_field_offset) |= ARC_ACTIVE; } inline void DDgraph::deactivate(Arc_type * arc) { *(arc + _data_field_offset) &= ~ARC_ACTIVE; } inline Statement * DDgraph::target_stmt(Arc_type * arc) const { return *(Statement **) arc; } inline Expression * DDgraph::target_expr(Arc_type * arc) const { return *(Expression **) (arc + _tgt_expr_offset); } inline Expression * DDgraph::label_expr(Arc_type * arc) const { return *(Expression **) (arc + _label_offset); } inline Arc_type * DDgraph::next_arc(Arc_type * arc) const { return *(Arc_type **) (arc + _next_arc_offset); } inline Arc_type * DDgraph::data_field(Arc_type * arc) const { return arc + _data_field_offset; } inline void DDgraph::store_target_stmt(Arc_type * arc, const Statement & stmt) { *(Statement **) arc = (Statement *) &stmt; } inline void DDgraph::store_target_expr(Arc_type * arc, const Expression & expr) { *(Expression **) (arc + _tgt_expr_offset) = (Expression *) &expr; } inline void DDgraph::store_label_expr(Arc_type * arc, const Expression & expr) { *(Expression **) (arc + _label_offset) = (Expression *) &expr; } inline void DDgraph::store_next_arc(Arc_type * arc, Arc_type * next) { *(Arc_type **) (arc + _next_arc_offset) = next; } inline DEP_DIREC DDgraph::test_dep_direction(Arc_type * arc_field, int offset) { return (DEP_DIREC) _test_1bit_field(arc_field, offset); } inline Arc_type DDgraph::_test_1bit_field(Arc_type * arc_field, int offset) { if (offset >= A_BYTE) return arc_field[offset / A_BYTE] << offset % A_BYTE & ARC_1_BIT; return *arc_field << offset & ARC_1_BIT; } inline void DDgraph::_skip_this_dvfield(Arc_type * &arc_field, int &position) { if ((position += DVF_DIREC) >= A_BYTE) { position -= A_BYTE; ++arc_field; } while (_DELIM != direction(arc_field, position)) { DDIST_TYPE t = min_distance(arc_field, position); t = max_distance(arc_field, position); ///< nothing else to do } } inline int DDgraph::_count_this_dvfield(Arc_type * &arc_field, int &position) { int bits = CONST_BITS; if ((position += DVF_DIREC) >= A_BYTE) { position -= A_BYTE; ++arc_field; } while (_DELIM != direction(arc_field, position)) { bits += (THREE_BIT + EIGHT_BIT + EIGHT_BIT); DDIST_TYPE t = min_distance(arc_field, position); t = max_distance(arc_field, position); } return bits; } inline void DDgraph::exit(DVfield * dvf, ActiveArc * active_arc) { release(dvf, active_arc); ///< This active_arc isn't empty but check if no more iterators use this if (active_arc && !--active_arc->_references) { ///< no iterator refers to this arc write_back_arc(active_arc); } } inline void DDgraph::hold(DVfield * dvf) { dvf->references_inc(); } inline void DDgraph::mark_dead(DVfield * dvf) { dvf->valid_off(); } inline Binary_flag DDgraph::is_alive(DVfield * dvf) { return dvf->_valid; } inline Binary_flag DDgraph::is_shared(DVfield * dvf) { return (dvf->_references>1); } inline DVfield * DDgraph::detach(DVfield * dvf, ActiveArc * active_arc) { return active_arc->_working_dv_fields.grab(*dvf); } inline List<DVfield> * DDgraph::dvfield_list(ActiveArc * active_arc) { return &active_arc->_working_dv_fields; } inline DDiterator::DDiterator(const Statement & from_stmt, const Expression & from_expr, const Statement & to_stmt, const Expression & to_expr, DDgraph & ddgraph) : _ddgraph(ddgraph) { _from_stmt = &from_stmt; _to_stmt = &to_stmt; _from_expr = &from_expr; _to_expr = &to_expr; _init_from = _init_to = _EXPR; _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _FIRST, from_stmt, from_expr, to_stmt, to_expr); } inline DDiterator::~DDiterator() { if (_current_dvf && _active_arc) _ddgraph.exit(_current_dvf, _active_arc); if (_init_from == _STMTS) { delete _iter_from_stmts; delete _iter_from_exprs; delete _from_stmts; } if (_init_to == _STMTS) { delete _iter_to_stmts; delete _iter_to_exprs; delete _to_stmts; } } inline Boolean DDiterator::valid() { return (_current_dvf ? True : False); } inline Boolean DDiterator::end() { return !valid(); } inline DVfield & DDiterator::current() { p_assert(current_valid(), "Try to access a dead object"); return *_current_dvf; } inline Boolean DDiterator::current_valid() { return ((_current_dvf && _ddgraph.is_alive(_current_dvf) ) ? True : False); } inline Boolean DDiterator::current_invalid() { return !current_valid(); } inline DVfield * DDiterator::grab() { p_assert(current_valid(), "Try to grab a dead object"); _ddgraph.mark_dead(_current_dvf); DVfield * dvf = (DVfield *) _current_dvf->listable_clone(); /* DVfield * dvf = new DVfield(_current_dvf->dep_decided(), _current_dvf->dep_type(), _current_dvf->from_stmt(), _current_dvf->from_expr(), _current_dvf->to_stmt(), _current_dvf->to_expr()); */ Iterator<ElementDV> iter = _current_dvf->dv(); for (; iter.valid(); ++iter) dvf->dv().ins_last(new ElementDV(iter.current())); return dvf; } inline void DDiterator::del() { p_assert(current_valid(), "Try to delete a dead object"); _ddgraph.mark_dead(_current_dvf); } inline void DDiterator::modify(DVfield * other) { p_assert(current_valid(), "Try to modify a dead object"); _ddgraph.mark_dead(_current_dvf); _ddgraph.dvfield_list(_active_arc)->ins_after(other, _current_dvf); _ddgraph.release(_current_dvf, _active_arc); _ddgraph.hold(other); _current_dvf = other; } ///< DVcapsule is for the routine merge_DVs() only struct DVcapsule { DVfield * dvf; DVcapsule * next; Binary_flag alive; DVcapsule(DVfield * dvf_ptr) { dvf = dvf_ptr; next = 0; alive = 1; ///< Initially alive } Binary_flag is_alive() { return alive; } void mark_dead() { alive = 0; } }; ///< Perform merge operation on all the DVfields in 'dvfs'. ///< Ex: (<,>) + (=,>) --> (<=,>) where the values of the other fields ///< in both the DVfields are the same. ///< The original list of 'dvfs' will be changed to have the merged list void merge_DVs(List<DVfield> & dvfs); ///< _dispose_capsules() recursively deletes all the DVcapsules hanging to the ///< corresponding Slots void _dispose_capsules(DVcapsule *& dvc); ///< With (<=, *) and (=, <>), the second is the proper subdirection.. ///< Nonproper subdirection will also be removed; that means the same ///< directions are to be removed such as (<, >=) & (<, >=). void _remove_all_subdirections(DVcapsule ** Slots, int levels); ///< Find the parent node, if any, for 'dvc' and some DVcapsule in 'list', and ///< create the new DVcapsule for that and add the the parent slot, 'Slot'. ///< Return the pointer to the capsule in 'list' if found. ///< Return 0 if there is not such a DVcapsule in 'list'. DVcapsule * _create_parent(DVcapsule *& Slot,DVcapsule * dvc,DVcapsule * list); ///< _is_parent_for() _is_subdirecion() and _is_same() are used ///< in merge_DVs() only. The dimension of two DVs must be the same... ///< otherwise, false will be returned. Binary_flag _is_parent_for(Iterator<ElementDV> & citer, Iterator<ElementDV> & piter); inline Binary_flag _is_same(Iterator<ElementDV> & iter1, Iterator<ElementDV> & iter2); Binary_flag _is_subdirecion(Iterator<ElementDV> & iter1, Iterator<ElementDV> & iter2); ///<///////////////////// Implementation inline Binary_flag _is_same(Iterator<ElementDV> & iter1, Iterator<ElementDV> & iter2) { iter1.reset(); iter2.reset(); for (; iter1.valid() && iter2.valid(); ++iter1, ++iter2) if (iter1.current().direction() != iter2.current().direction()) return 0; if (iter1.end() && iter2.end()) return 1; else return 0; } void ddtests_main(Program&, DDtests_Seq, Binary_flag); #endif

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:44 2005