ReachingDefinitions.cpp

#include "DataFlowAnalysis.h"

#include <iostream>

namespace DFA {

	ReachingDefinitions::ReachingDefinitions(BasicBlock_list_sptr bbs) : _bbs(bbs) {
		auto counter = 1;

		// Compute Def[t], where t is a 'variable' name and Def[*] is a list of all
		// instructions that define 't'.
		for (auto& bb : *_bbs) {
			for (auto& ins : bb->instructions()) {
				auto instr = ins.shared_from_this();

				if ( IR::isADefinition(instr) ) {
					auto tgt = *instr->defs()->begin();

					if (_defs.find(tgt) == _defs.end())
						_defs[tgt] = make_shared<Instruction_set>();

					this->_defs[tgt]->insert(instr);
				}
			}
		}

		// Compute the Kill[i] and Gen[i] sets, where 'i' is an instruction
		// and Kill[*] is the set of all instruction/definitions that are killed by
		// the current instruction and Gen[i] is the set of instruction/definitions
		// generated by the current instruction.
		for (auto& bb : *_bbs) {
			_inBb[bb] = make_shared<Instruction_set>();
			_outBb[bb] = make_shared<Instruction_set>();

			for (auto& ins : bb->instructions()) {
				auto instr = ins.shared_from_this();

				_identifier[instr] = counter++;

				if ( IR::isADefinition(instr) ) {
					_gen[instr] = make_shared<Instruction_set>();
					_gen[instr]->insert(instr);

					_kill[instr] = make_shared<Instruction_set>();

					auto df = _defs[ *instr->defs()->begin() ];

					std::set_difference(df->begin(), df->end(), 
										_gen[instr]->begin(), _gen[instr]->end(), 
										std::inserter(*_kill[instr], _kill[instr]->begin()));
				}
				else {
					_gen[instr] = make_shared<Instruction_set>();
					_kill[instr] = make_shared<Instruction_set>();
				}

				_inInstr[instr] = make_shared<Instruction_set>();
				_outInstr[instr] = _gen[instr];
			}
		}
	}



	// Execute reaching definitions. Up to this point In and Out of basic blocks are empty.
	// Kill and Gen of each instruction is already computed.
	void ReachingDefinitions::execute() {
		bool hadChanges = true;

		while (hadChanges) {
			hadChanges = false;			

			for (auto& bb : *_bbs) {
				// This represents the UNION of OUT of previous BBs/Instructions
				auto prevOut = make_shared<Instruction_set>();

				// for each predecessor basic block
				auto preds = *bb->preds();
				for (auto pred : preds) {
					auto lastOut = _outBb[pred];

					// This is just to contain tmp Unions
					auto tmpRes = make_shared<Instruction_set>();

					// Add together the OUT of the last bb with the OUT of the current one
					std::set_union(	prevOut->begin(), prevOut->end(), 
									lastOut->begin(), lastOut->end(), 
									std::inserter(*tmpRes, tmpRes->begin()));

					prevOut = tmpRes;
				}

				// Input of current basic block
				_inBb[bb] = prevOut;

				// So the in of the first instruction is the UNION of the OUT of 
				// the predecessors. In the case of the first instruction of the BB the OUT
				// is the UNION of OUT's of all predecessors.
				// Now compute the IN/OUT of each instruction
				for (auto& ins : bb->instructions()) {
					auto instr = ins.shared_from_this();

					_inInstr[instr] = prevOut;

					auto tmpOut = make_shared<Instruction_set>();

					// Add together the OUT of the last bb with the OUT of the current one
					std::set_difference(_inInstr[instr]->begin(), _inInstr[instr]->end(), 
										_kill[instr]->begin(), _kill[instr]->end(), 
										std::inserter(*tmpOut, tmpOut->begin()));

					auto newOut = make_shared<Instruction_set>();

					std::set_union(_gen[instr]->begin(), _gen[instr]->end(), 
									tmpOut->begin(), tmpOut->end(), 
									std::inserter(*newOut, newOut->begin()));

					if (*_outInstr[instr] != *newOut) {
						hadChanges = true;	
						_outInstr[instr] = newOut;
					}

					prevOut = newOut;
				}

				_outBb[bb] = prevOut;
			}
		}
	}


	void ReachingDefinitions::dump() {
		stringstream output;

		output << "Reaching definitions dump output: " << endl;

		for (auto& bb : *_bbs) {
			output << "BB" << bb->id() << ":" << endl;

			for (auto& ins : bb->instructions()) {
				auto instr = ins.shared_from_this();

				output << std::setw(3) << _identifier[instr] << ": ";
				instr->dump(output);

				output << "\t|-> IN {";
				for (auto in : *_inInstr[instr]) {
					output << _identifier[in] << " ";
				}	

				output << "} OUT { ";
				for (auto out : *_outInstr[instr]) {
					output << _identifier[out] << " ";
				}	

				output << "} KILL { ";
				for (auto out : *_kill[instr]) {
					output << _identifier[out] << " ";
				}	

				output << "} GEN { ";
				for (auto out : *_gen[instr]) {
					output << _identifier[out] << " ";
				}	
				output << "} " << endl;
			}
		}

		cout << output.str() << endl;
	}
}