tools/pldt/org.eclipse.ptp.pldt.mpi.analysis/src/org/eclipse/ptp/pldt/mpi/analysis/analysis/MPISSA.java

/**********************************************************************
 * Copyright (c) 2007 IBM Corporation.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/

package org.eclipse.ptp.pldt.mpi.analysis.analysis;

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import org.eclipse.cdt.core.dom.ast.ASTVisitor;
import org.eclipse.cdt.core.dom.ast.IASTDoStatement;
import org.eclipse.cdt.core.dom.ast.IASTForStatement;
import org.eclipse.cdt.core.dom.ast.IASTStatement;
import org.eclipse.cdt.core.dom.ast.IASTWhileStatement;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IBlock;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraph;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.ICallGraphNode;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.IControlFlowGraph;
import org.eclipse.ptp.pldt.mpi.analysis.cdt.graphs.impl.Block;

public class MPISSA {
	protected ICallGraph cg_;
	protected MPICallGraphNode currentFunc_;
	protected Hashtable<String,List<IBlock>> defTable_;
	protected IControlFlowGraph cfg_;
	
	public MPISSA(ICallGraph cg){
		cg_ = cg;
	}
	
	public void run(){
		for(ICallGraphNode n = cg_.botEntry(); n != null; n = n.botNext()){
			MPICallGraphNode node = (MPICallGraphNode)n;
			//System.out.println(node.getFuncName());
			if(!node.marked) continue;
			currentFunc_ = node;
			cfg_ = node.getCFG();
			defTable_ = node.getDefTable();
			domFrontier();
			placePHI();
			ExitBlockPhi ebp = new ExitBlockPhi();
			ebp.run();
		}
	}
	
	public void domFrontier(){
		for(IBlock bx = cfg_.getEntry(); bx != null; bx = bx.topNext()){
			MPIBlock x = (MPIBlock)bx;
			List<IBlock> DF = new ArrayList<IBlock>();
			for(IBlock by = cfg_.getEntry(); by != null; by = by.topNext()){
				MPIBlock y = (MPIBlock)by;
				for(Iterator<IBlock> i = y.getPreds().iterator(); i.hasNext();){
					MPIBlock pred = (MPIBlock)i.next();
					if(pred.getDOM().contains(x) && !(y.getDOM().contains(x) && x != y)){
						if(!DF.contains(y)) DF.add(y);
					}
				}
			}
			x.setDF(DF);
		}
	}
	
	public void placePHI(){
		int iterCount = 0;
		for(IBlock b = cfg_.getEntry(); b != null; b = b.topNext()){
			MPIBlock block = (MPIBlock)b;
			block.hasAlready = 0;
			block.work = 0;
		}
		LinkedList<IBlock> W = new LinkedList<IBlock>();
		for(Enumeration<String> e = defTable_.keys(); e.hasMoreElements();){
			String var = e.nextElement();
			iterCount ++;
			List<IBlock> defs = defTable_.get(var);
			for(Iterator<IBlock> i = defs.iterator(); i.hasNext();){
				MPIBlock defblock = (MPIBlock)i.next();
				defblock.work = iterCount;
				W.add(defblock);
			}
			while(!W.isEmpty()){
				MPIBlock next = (MPIBlock)W.remove();
				for(Iterator<IBlock> i = next.getDF().iterator(); i.hasNext();){
					MPIBlock df = (MPIBlock)i.next();
					if(df.hasAlready < iterCount){
						if(df.getCond() == null && df != cfg_.getExit()){ 
							//no associated condition?
							System.out.println("Error: phi Node has no condition!" +  //$NON-NLS-1$
									currentFunc_.getFuncName() + " Block " + df.getID()); //$NON-NLS-1$
							//return;
						}
						df.setPhi();
						if(!df.getDef().contains(var)) df.getDef().add(var);
						//if(!df.getUse().contains(var)) df.getUse().add(var);
						if(df.getUse().contains(var) && !df.getUsedPhiVar().contains(var))
							df.getUsedPhiVar().add(var);
						if(!df.getPhiVar().contains(var)) df.getPhiVar().add(var);
						if(!defs.contains(df)) defs.add(df);
						updateDefTable(df, var);
						//System.out.println("Block " + df.getID() + " has Phi for " + var);
						df.hasAlready = iterCount;
						if(df.work < iterCount){
							df.work = iterCount;
							W.add(df);
						}
					}
				}
			}
		}
		for(IBlock b = cfg_.getEntry(); b != null; b = b.topNext()){
			MPIBlock block = (MPIBlock)b;
			if(block.hasPhi())
				for(Iterator<String> i = block.getPhiVar().iterator(); i.hasNext();){
					String var = i.next();
					if(!block.getUse().contains(var))
						block.getUse().add(var);
				}
		}
	}
	
	protected void updateDefTable(IBlock block, String var){
		List<IBlock> list = defTable_.get(var);
		if(list == null){
			System.out.print("Error in SSA!"); //$NON-NLS-1$
			return;
		}
		if(!list.contains(block))
			list.add(block);
	}
	
	class ExitBlockPhi extends ASTVisitor{
		
		public void run(){
			this.shouldVisitStatements = true;
			this.shouldVisitDeclarations = true;
			currentFunc_.getFuncDef().accept(this);
		}
		
		public int visit(IASTStatement stmt){
			MPIBlock condblock = null;
			if(stmt instanceof IASTDoStatement){
				IASTDoStatement doS = (IASTDoStatement)stmt;
				condblock = (MPIBlock)cfg_.getBlock(doS.getCondition(), stmt);
			}
			else if(stmt instanceof IASTForStatement){
				IASTForStatement forS = (IASTForStatement)stmt;
				condblock = (MPIBlock)cfg_.getBlock(forS.getConditionExpression(), stmt);
			}
			else if(stmt instanceof IASTWhileStatement){
				IASTWhileStatement whileS = (IASTWhileStatement)stmt;
				condblock = (MPIBlock)cfg_.getBlock(whileS.getCondition(), stmt);
			} 
			else {
				return PROCESS_CONTINUE;
			}
			
			MPIBlock exitblock = null;
			for(Iterator<IBlock> i = condblock.getSuccs().iterator(); i.hasNext();){
				MPIBlock succ = (MPIBlock)i.next();
				if(succ.getType() == Block.exit_join_type)
					exitblock = succ;
			}
			
			exitblock.setPhi();
			for(Iterator<String> i = condblock.getPhiVar().iterator(); i.hasNext();){
				String phivar = i.next();
				if(!exitblock.getDef().contains(phivar))
					exitblock.getDef().add(phivar);
				if(!exitblock.getUse().contains(phivar))
					exitblock.getUse().add(phivar);
				if(!exitblock.getPhiVar().contains(phivar))
					exitblock.getPhiVar().add(phivar);
				updateDefTable(exitblock, phivar);
			}
			
			return PROCESS_CONTINUE;
		}
	}

}