00001 /* -*- Mode: C++; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 #ifndef __J2S_GRAPH_ALG_H
00003 #define __J2S_GRAPH_ALG_H
00004
00005 /*
00006 * $Id: j2s_graph_alg.h,v 1.2 2000/07/24 00:33:01 brm Exp $
00007 */
00008
00009
00010 /*
00011 * This class contain various graph algorithms:
00012 * - graph coloring by root -- Does this make sense???
00013 * Maybe the algorithms is too naive !!!
00014 * - is x anchestor of y?
00015 * - x dom y
00016 * - is graph reducible?
00017 *
00018 * We use the terminology of ASU86 in comments and names.
00019 * Most algorithms destroy the _markers of the basic blocks!
00020 *
00021 * !!! We do not handle exception control flow, i.e. the root of the CFG
00022 * !!! is the first basic block in the code array and exception edges in the CFG
00023 * !!! are ignored.
00024 */
00025 class j2s_GraphAlg {
00026 private:
00027 j2s_GraphAlg(j2s_GraphAlg&);
00028 j2s_GraphAlg& operator=(j2s_GraphAlg&);
00029
00030 j2s_BasicBlocks* _bbs;
00031
00032 static const char* const _dfst_number_annotation_name;
00033 static const char* const _dfst_edges_annotation_name;
00034
00035 static const char* const _retreating_edge_str;
00036 static const char* const _advancing_edge_str;
00037 static const char* const _cross_edge_str;
00038
00039 void init_edge_descriptors();
00040 void build_edge_descriptor();
00041 void color_graph_by_root(j2s_BasicBlock* bb, j2s_BasicBlock* root);
00042 bool dom_search(j2s_BasicBlock* bb, jhl_u4 head, jhl_u4 tail);
00043 void dfst_search(j2s_BasicBlock* bb, int* dfst_number);
00044
00045 public:
00046 j2s_GraphAlg(j2s_BasicBlocks* bbs) : _bbs(bbs) { }
00047
00048 bool all_blocks_marked();
00049 bool is_retreating_edge(j2s_BasicBlock* from_block, jhl_u4 to_node);
00050 bool is_back_edge(j2s_BasicBlock* from_block, jhl_u4 to_node);
00051 bool is_anchestor(j2s_BasicBlock* start_block, jhl_u4 target_node);
00052 bool dom(jhl_u4 head, jhl_u4 tail);
00053
00054 void color_graph_by_root();
00055 void build_dfst();
00056 bool graph_is_reducible();
00057 #ifdef CFG
00058 void annotate_suif_cfg();
00059 #endif
00060 };
00061
00062
00063 #endif /* __J2S_GRAPH_ALG_H */
