havlak6.cc

#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Block {
public:
	Block(int n) : name(n) {}

	int name;
	vector<Block*> in;
	vector<Block*> out;

	string String();
	void Dump(FILE*);
};

string Block::String() {
	char buf[20];
	snprintf(buf, sizeof buf, "b%d", this->name);
	return buf;
}

void Block::Dump(FILE *f) {
	fprintf(f, "%s: [", this->String().c_str());
	for (int i = 0; i < this->in.size(); i++)
		fprintf(f, "%s%s", i > 0 ? " " : "", this->in[i]->String().c_str());
	fprintf(f, "] [");
	for (int i = 0; i < this->out.size(); i++)
		fprintf(f, "%s%s", i > 0 ? " " : "", this->out[i]->String().c_str());
	fprintf(f, "]\n");
}

struct Edge {
	Edge(int s, int d) : src(s), dst(d) {}
	int src, dst;
};

class CFG {
public:
	vector<Block*> block;
	vector<Edge> edge;

	Block *NewBlock();
	void Connect(Block *src, Block *dst);
	Block *Path(Block *from);
	Block *Diamond(Block *from);
	Block *BaseLoop(Block *from);
	void Dump(FILE*);
};

Block *CFG::NewBlock() {
	Block *b = new Block(this->block.size());
	this->block.push_back(b);
	return b;
}

void CFG::Dump(FILE *f) {
	for (int i = 0; i < this->block.size(); i++)
		this->block[i]->Dump(f);
}

void CFG::Connect(Block *src, Block *dst) {
	src->out.push_back(dst);
	dst->in.push_back(src);
	this->edge.push_back(Edge(src->name, dst->name));
}

Block *CFG::Path(Block *from) {
	Block *n = this->NewBlock();
	this->Connect(from, n);
	return n;
}

Block *CFG::Diamond(Block *from) {
	Block *x = this->Path(from);
	Block *y = this->Path(from);
	Block *z = this->Path(x);
	this->Connect(y, z);
	this->Connect(z, from);
	return z;
}

Block *CFG::BaseLoop(Block *from) {
	Block *z = this->Path(this->Diamond(this->Path(this->Diamond(this->Path(from)))));
	this->Connect(z, from);
	return this->Path(z);
}

CFG *BuildGraph() {
	CFG *g = new CFG;
	
	Block *n0 = g->NewBlock();
	Block *n1 = g->NewBlock();
	Block *n2 = g->NewBlock();
	g->Connect(n0, n2);
	
	for (int i = 0; i < 10; i++) {
		Block *n = g->NewBlock();
		g->Connect(n2, n);

		for (int j = 0; j < 100; j++) {
			Block *top = n;
			n = g->Path(n);
			for (int k = 0; k < 25; k++) {
				n = g->BaseLoop(n);
			}
			Block *bottom = g->Path(n);
			g->Connect(n, top);
			n = bottom;
		}
		g->Connect(n, n1);
	}
	return g;
}

// Basic representation of loop graph.

class Loop {
public:
	vector<Block*> block;
	vector<Loop*> child;
	Loop *parent;
	Block *head;
	
	bool isRoot;
	bool isReducible;
	int counter;
	int nesting;
	int depth;

};

class LoopGraph {
public:
	Loop root;
	vector<Loop*> loop;
	~LoopGraph();

	Loop *NewLoop(int cap);
	void CalculateNesting();
	void calculateNesting(Loop* l, int depth);
};

LoopGraph::~LoopGraph() {
	for (int i = 0; i < this->loop.size(); i++)
		delete this->loop[i];
}

static int loopCounter = 0;

Loop *LoopGraph::NewLoop(int cap) {
	loopCounter++;
	Loop *l = new Loop;
	l->counter = loopCounter;
	l->block.reserve(cap);
	this->loop.push_back(l);
	return l;
}

void LoopGraph::CalculateNesting() {
	for (int i = 0; i < this->loop.size(); i++) {
		Loop *l = this->loop[i];
		if (l->isRoot)
			continue;
		if (l->parent == NULL) {
			l->parent = &this->root;
			this->root.child.push_back(l);
		}
	}
	this->calculateNesting(&this->root, 0);
}

void LoopGraph::calculateNesting(Loop *l, int depth) {
	l->depth = depth;
	for (int i = 0; i < l->child.size(); i++) {
		Loop *child = l->child[i];
		this->calculateNesting(child, depth+1);
		int n = child->nesting + 1;
		if (l->nesting < n)
			l->nesting = n;
	}
}

// TODO: Dump, String

// Loop finding state, generated or reused on each iteration.

class LoopBlock {
public:
	enum Type {
		NonHeader,
		Reducible,
		Self,
		Irreducible,
		Dead,
	};

	Block *block;
	Loop *loop;
	int first;
	int last;
	LoopBlock *header; // TODO: head
	Type type;
	vector<LoopBlock*> backPred;
	vector<LoopBlock*> nonBackPred;
	LoopBlock *unionf;

	void Init(Block*);
	LoopBlock *Find();
	bool IsAncestor(LoopBlock*);
	
};

class LoopFinder {
public:
	vector<LoopBlock> loopBlock;
	vector<LoopBlock*> depthFirst;
	vector<LoopBlock*> pool;

	void Search(Block*);
	void FindLoops(CFG*, LoopGraph*);
};

const int Unvisited = -1;

void LoopBlock::Init(Block *b) {
	this->block = b;
	this->loop = NULL;
	this->first = Unvisited;
	this->last = Unvisited;
	this->header = NULL;
	this->type = LoopBlock::NonHeader;
	this->backPred.clear();
	this->nonBackPred.clear();
	this->unionf = this;
}

LoopBlock *LoopBlock::Find() {
	if (this->unionf != this) {
		this->unionf = this->unionf->Find();
	}
	return this->unionf;
}

// Depth first search to number blocks.

void LoopFinder::Search(Block *b) {
	LoopBlock *lb = &this->loopBlock[b->name];
	this->depthFirst.push_back(lb);
	lb->first = this->depthFirst.size();
	for (int i = 0; i < b->out.size(); i++) {
		Block *out = b->out[i];
		if (this->loopBlock[out->name].first == Unvisited)
			this->Search(out);
	}
	lb->last = this->depthFirst.size();
}

bool LoopBlock::IsAncestor(LoopBlock *p) {
	return this->first <= p->first && p->first <= this->last;
}

void LoopFinder::FindLoops(CFG *g, LoopGraph *lsg) {
	int size = g->block.size();
	if (size == 0)
		return;

	// Step A: Initialize nodes, depth first numbering, mark dead nodes.
	this->loopBlock.resize(size);
	this->depthFirst.reserve(size);
	this->depthFirst.clear();
	for (int i = 0; i < size; i++)
		this->loopBlock[i].Init(g->block[i]);
	this->Search(g->block[0]);
	for (int i = 0; i < size; i++ ){
		LoopBlock *lb = &this->loopBlock[i];  // TODO
		if (lb->first == Unvisited)
			lb->type = LoopBlock::Dead;
	}

	// Step B: Classify back edges as coming from descendents or not.
	for (int i = 0; i < this->depthFirst.size(); i++) {
		LoopBlock *lb = this->depthFirst[i];
		for (int j = 0; j < lb->block->in.size(); j++) {
			Block *b = lb->block->in[j];
			LoopBlock *lbb = &this->loopBlock[b->name];  // TODO
			if (lb->IsAncestor(lbb))
				lb->backPred.push_back(lbb);
			else
				lb->nonBackPred.push_back(lbb);
		}
	}

	// Start node is root of all other loops.
	this->loopBlock[0].header = &this->loopBlock[0];

	// Step C:
	//
	// The outer loop, unchanged from Tarjan. It does nothing except
	// for those nodes which are the destinations of backedges.
	// For a header node w, we chase backward from the sources of the
	// backedges adding nodes to the set P, representing the body of
	// the loop headed by w.
	//
	// By running through the nodes in reverse of the DFST preorder,
	// we ensure that inner loop headers will be processed before the
	// headers for surrounding loops.
	for (int i = this->depthFirst.size() - 1; i >= 0; i--) {
		LoopBlock *w = this->depthFirst[i];

		this->pool.clear();

		// Step D.
		for (int i = 0; i < w->backPred.size(); i++) {
			LoopBlock* pred = w->backPred[i];
			if (w == pred) {
				w->type = LoopBlock::Self;
				continue;
			}
			this->pool.push_back(pred->Find());
		}

		// Process node pool in order as work list.
		for (int i = 0; i < this->pool.size(); i++) {
			LoopBlock *x = this->pool[i];

			// Step E:
			//
			// Step E represents the main difference from Tarjan's method.
			// Chasing upwards from the sources of a node w's backedges. If
			// there is a node y' that is not a descendant of w, w is marked
			// the header of an irreducible loop, there is another entry
			// into this loop that avoids w->
			for (int j = 0; j < x->nonBackPred.size(); j++) {
				LoopBlock *y = x->nonBackPred[j];
				LoopBlock *ydash = y->Find();
				if (!w->IsAncestor(ydash)) {
					w->type = LoopBlock::Irreducible;
					if (find(w->nonBackPred.begin(), w->nonBackPred.end(), y) == w->nonBackPred.end())
						w->nonBackPred.push_back(y);
				} else if (ydash != w) {
					if (find(this->pool.begin(), this->pool.end(), ydash) == this->pool.end())
						this->pool.push_back(ydash);
				}
			}
		}

		// Collapse/Unionize nodes in a SCC to a single node
		// For every SCC found, create a loop descriptor and link it in.
		if (this->pool.size() > 0 || w->type == LoopBlock::Self) {
			Loop *l = lsg->NewLoop(1 + pool.size());
			l->head = w->block;
			l->block.push_back(w->block);
			l->isReducible = w->type != LoopBlock::Irreducible;
			w->loop = l;

			// At this point, one can set attributes to the loop, such as:
			//
			// the bottom node:
			//    iter  = backPreds[w].begin();
			//    loop bottom is: nodes[iter].node);
			//
			// the number of backedges:
			//    backPreds[w].size()
			for (int i = 0; i < pool.size(); i++) {
				LoopBlock *node = pool[i];
				// Add nodes to loop descriptor.
				node->header = w;
				node->unionf = w;

				// Nested loops are not added, but linked together.
				if (node->loop != NULL) {
					node->loop->parent = l;
				} else {
					l->block.push_back(node->block);
				}
			}
		}
	}
}

// Main program.

int main() {
	LoopFinder f;
	
	CFG *g = BuildGraph();
	LoopGraph lsg;
	f.FindLoops(g, &lsg);
	
	for (int i = 0; i < 50; i++) {
		LoopGraph lsg;
		f.FindLoops(g, &lsg);
	}

	printf("# of loops: %d (including 1 artificial root node)\n", (int)lsg.loop.size());
	lsg.CalculateNesting();
}