You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
172 lines
6.0 KiB
172 lines
6.0 KiB
/******************************************************************************
|
|
* Copyright (C) 2020-2021 Dibyendu Majumdar
|
|
*
|
|
* Permission is hereby granted, free of charge, to any person obtaining
|
|
* a copy of this software and associated documentation files (the
|
|
* "Software"), to deal in the Software without restriction, including
|
|
* without limitation the rights to use, copy, modify, merge, publish,
|
|
* distribute, sublicense, and/or sell copies of the Software, and to
|
|
* permit persons to whom the Software is furnished to do so, subject to
|
|
* the following conditions:
|
|
*
|
|
* The above copyright notice and this permission notice shall be
|
|
* included in all copies or substantial portions of the Software.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
|
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
|
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
|
|
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
|
|
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
|
|
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
|
|
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
|
******************************************************************************/
|
|
|
|
#include "dominator.h"
|
|
|
|
#include "graph.h"
|
|
#include "ravi_compiler.h"
|
|
|
|
#include <assert.h>
|
|
|
|
/*
|
|
* The dominator tree construction algorithm is based on figure 9.24,
|
|
* chapter 9, p 532, of Engineering a Compiler.
|
|
*
|
|
* The algorithm is also described in the paper 'A Simple, Fast
|
|
* Dominance Algorithm' by Keith D. Cooper, Timothy J. Harvey and
|
|
* Ken Kennedy.
|
|
*/
|
|
|
|
/*
|
|
Some terminology:
|
|
|
|
DOM(b): A node n in the CFG dominates b if n lies on every path from the entry node of the CFG to b.
|
|
DOM9b) contains every node n that dominates b.
|
|
|
|
IDOM(b): For a node b, the set IDOM(b) contains exactly one node, the immediate dominator of b.
|
|
If n is b's immediate dominator then every node in {DOM(b) - b} is also in DOM(n).
|
|
|
|
The dominator tree algorithm is an optimised version of forward data flow solver. The
|
|
algorithm iterates until a fixed point is reached. The output of the algorithm is the IDOM
|
|
array that describes the dominator tree.
|
|
*/
|
|
|
|
struct DominatorTree {
|
|
Graph *g;
|
|
GraphNode **IDOM; /* IDOM[] - array of immediate dominators, one per node in the graph, indexed by node id */
|
|
uint32_t N; /* sizeof IDOM */
|
|
};
|
|
|
|
DominatorTree *raviX_new_dominator_tree(Graph *g)
|
|
{
|
|
DominatorTree *state = (DominatorTree *)raviX_calloc(1, sizeof(DominatorTree));
|
|
state->N = raviX_graph_size(g);
|
|
state->IDOM = (GraphNode **)raviX_calloc(state->N, sizeof(GraphNode *));
|
|
state->g = g;
|
|
return state;
|
|
}
|
|
|
|
void raviX_destroy_dominator_tree(DominatorTree *state)
|
|
{
|
|
raviX_free(state->IDOM);
|
|
raviX_free(state);
|
|
}
|
|
|
|
/* Finds nearest common ancestor */
|
|
/* The algorithm starts at the two nodes whose sets are being intersected, and walks
|
|
* upward from each toward the root. By comparing the nodes with their RPO numbers
|
|
* the algorithm finds the common ancestor - the immediate dominator of i and j.
|
|
*/
|
|
static GraphNode *intersect(DominatorTree *state, GraphNode *i, GraphNode *j)
|
|
{
|
|
GraphNode *finger1 = i;
|
|
GraphNode *finger2 = j;
|
|
while (finger1 != finger2) {
|
|
while (raviX_node_RPO(finger1) > raviX_node_RPO(finger2)) {
|
|
finger1 = state->IDOM[raviX_node_index(finger1)];
|
|
assert(finger1);
|
|
}
|
|
while (raviX_node_RPO(finger2) > raviX_node_RPO(finger1)) {
|
|
finger2 = state->IDOM[raviX_node_index(finger2)];
|
|
assert(finger2);
|
|
}
|
|
}
|
|
return finger1;
|
|
}
|
|
|
|
/* Look for the first predecessor whose immediate dominator has been calculated.
|
|
* Because of the order in which this search occurs, we will always find at least 1
|
|
* such predecessor.
|
|
*/
|
|
static GraphNode *find_first_predecessor_with_idom(DominatorTree *state, GraphNodeList *predlist)
|
|
{
|
|
for (uint32_t i = 0; i < raviX_node_list_size(predlist); i++) {
|
|
nodeId_t id = raviX_node_list_at(predlist, i);
|
|
if (state->IDOM[id])
|
|
return raviX_graph_node(state->g, id);
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
/**
|
|
* Calculates the dominator tree.
|
|
* Before this is called the graph links should have been numbered in
|
|
* reverse post order.
|
|
*/
|
|
void raviX_calculate_dominator_tree(DominatorTree *state)
|
|
{
|
|
/*
|
|
Some implementation details:
|
|
The graph and links reference nodes by node ids.
|
|
However the IDOM array references the node objects - i.e.
|
|
pointers to 'GraphNode'. So we have some conversion from node id
|
|
to the node, and vice versa at various points.
|
|
*/
|
|
|
|
uint32_t N = raviX_graph_size(state->g);
|
|
GraphNode **nodes_in_reverse_postorder = raviX_graph_nodes_sorted_by_RPO(state->g, false);
|
|
for (uint32_t i = 0; i < state->N; i++) {
|
|
state->IDOM[i] = NULL; /* undefined - set to a invalid value */
|
|
}
|
|
// Set IDom entry for root to itself
|
|
state->IDOM[ENTRY_BLOCK] = raviX_graph_node(state->g, ENTRY_BLOCK);
|
|
bool changed = true;
|
|
while (changed) {
|
|
changed = false;
|
|
// for all nodes, b, in reverse postorder (except root)
|
|
for (uint32_t i = 0; i < N; i++) {
|
|
GraphNode *b = nodes_in_reverse_postorder[i];
|
|
nodeId_t bid = raviX_node_index(b);
|
|
if (bid == ENTRY_BLOCK) // skip root
|
|
continue;
|
|
GraphNodeList *predecessors = raviX_predecessors(b); // Predecessors of b
|
|
// NewIDom = first (processed) predecessor of b, pick one
|
|
GraphNode *firstpred = find_first_predecessor_with_idom(state, predecessors);
|
|
assert(firstpred != NULL);
|
|
GraphNode *NewIDom = firstpred;
|
|
// for all other predecessors, p, of b
|
|
for (uint32_t k = 0; k < raviX_node_list_size(predecessors); k++) {
|
|
nodeId_t pid = raviX_node_list_at(predecessors, k);
|
|
GraphNode *p = raviX_graph_node(state->g, pid);
|
|
if (p == firstpred)
|
|
continue; // all other predecessors
|
|
if (state->IDOM[raviX_node_index(p)] != NULL) {
|
|
// i.e. IDoms[p] calculated
|
|
NewIDom = intersect(state, p, NewIDom);
|
|
}
|
|
}
|
|
if (state->IDOM[bid] != NewIDom) {
|
|
state->IDOM[bid] = NewIDom;
|
|
changed = true;
|
|
}
|
|
}
|
|
}
|
|
raviX_free(nodes_in_reverse_postorder);
|
|
}
|
|
|
|
void raviX_dominator_tree_output(DominatorTree *tree, FILE *fp)
|
|
{
|
|
for (uint32_t i = 0; i < tree->N; i++) {
|
|
fprintf(stdout, "IDOM[%d] = %d\n", i, raviX_node_index(tree->IDOM[i]));
|
|
}
|
|
} |