tools/pldt/org.eclipse.ptp.pldt.openmp.analysis/src/org/eclipse/ptp/pldt/openmp/analysis/ompcfg/factory/RegionConcurrencyMap.java

/**********************************************************************
 * Copyright (c) 2006 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.openmp.analysis.ompcfg.factory;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;

import org.eclipse.cdt.core.dom.ast.IASTExpression;
import org.eclipse.cdt.core.dom.ast.IASTNode;
import org.eclipse.ptp.pldt.openmp.analysis.PAST.PASTOMPPragma;
import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPBasicBlock;
import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPCFG;
import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPCFGNode;
import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPDFS;
import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPExpressionBlock;
import org.eclipse.ptp.pldt.openmp.analysis.ompcfg.OMPPragmaNode;

/**
 * Builds the concurrency map and provides access to it 
 * @author pazel
 *
 */
public class RegionConcurrencyMap
{

    protected RegionConcurrencyAnalysis region_ = null;
    protected OMPCFG                    cfg_       = null;
    
    protected PhaseConcurrencyAnalysis []  phases_    = null;
    
    // The actual map
    protected ArrayList               indexMap_ = new ArrayList(); // index->stmt
    protected Hashtable               stmtMap_  = new Hashtable(); // stmt->index
    // stmt to BitSet, representing all statments concurrent to stmt
    protected Hashtable               concurrencyMap_ = new Hashtable();
    
    // Used in each phase process to list all nodes found
    protected LinkedList              phaseStmts_ = new LinkedList();
    
    
    // Some sub-regions need to exclude within themselves.  To help with this,
    // we build a iastnode-->OMPPragmaNode hashmap, used by the second part of processConcurrency
    protected Hashtable               exclusionMap_ = new Hashtable();
    
    /**
     * RegionConcurrencyMap - constructor
     * @param component - RegionConcurrencyAnalysis
     */
    public RegionConcurrencyMap(RegionConcurrencyAnalysis region)
    {
        region_    = region;
        cfg_       = region_.getCFG();
        phases_    = region_.getPhases();
    }
    
    /**
     * buildMap - build the concurrencyMap_ and other artifacts for the map
     *
     */
    public void buildMap()
    {
        for(int i=0; i<phases_.length; i++) 
            processPhase(phases_[i]);
    }
    
    /**
     * processPhase - process given phase into the concurrency map
     * @param phase - PhaseConcurrencyAnalysis
     */
    protected void processPhase(PhaseConcurrencyAnalysis phase)
    {
        Set nodes = phase.getNodes();  // of OMPCFGNode's
        phaseStmts_.clear();
        exclusionMap_.clear();
        
        OMPPragmaNode ePragma = null;    // exclusion pragma
        
        for(Iterator i=nodes.iterator(); i.hasNext();) {
            OMPCFGNode node = (OMPCFGNode)i.next();
            
            // Establish the exclusion context if any
            ePragma = node.getPragmaContext();
            if (ePragma!=null && ePragma.getPragma()!=null) {
                int pType = ePragma.getPragma().getOMPType();
                // if none of these situations, all the stmts in the node can execute concurrently to each other
                // (note: if single and has barrier free path to self, stmts can execute concurrently to each other
                if (!((pType==PASTOMPPragma.OmpSingle && !hasBarrierFreePathToSelf((OMPBasicBlock)node)) || 
                      pType==PASTOMPPragma.OmpMaster ||
                      pType==PASTOMPPragma.OmpOrdered || 
                      pType==PASTOMPPragma.OmpCritical || 
                      pType==PASTOMPPragma.OmpSection))
                    ePragma=null;
            }
            else 
                ePragma=null;
            
            if (node instanceof OMPBasicBlock) {
                LinkedList stmts = ((OMPBasicBlock)node).getFundamentals();
                for(Iterator j=stmts.iterator(); j.hasNext();) {
                    IASTNode n = (IASTNode)j.next();
                    indexNode(n, ePragma);
                }
                indexNode(((OMPBasicBlock)node).getBranchingExpression(), ePragma);
            }
            else if (node instanceof OMPExpressionBlock) {
                IASTExpression [] eList = ((OMPExpressionBlock)node).getExpressions();
                for(int j=0; j<eList.length; j++)
                    indexNode(eList[j], ePragma);
            }
        }
        
        // Go though the list of phase nodes, and 
        //    ASSUMING THEY ARE ALL CONCURRENT WITH EACH OTHER (will change later)
        // make them all concurrent to each other
        for(Iterator i=phaseStmts_.iterator(); i.hasNext();) {
            IASTNode  n = (IASTNode)i.next();
            OMPPragmaNode ePragmaS = (OMPPragmaNode)exclusionMap_.get(n);
            int       nIndex = ((Integer)(stmtMap_.get(n))).intValue();
            for(Iterator j=phaseStmts_.iterator(); j.hasNext();) {
                IASTNode m = (IASTNode)j.next();
                OMPPragmaNode ePragmaT = (OMPPragmaNode)exclusionMap_.get(m);
                
                // stmts in the same exclusion cannot be concurrent
                if (!(ePragmaT==ePragmaS && ePragmaT!=null)) {
                  BitSet   b = (BitSet)(concurrencyMap_.get(m));
                  b.set(nIndex);
                }
                
            }
        }
    }
    
    /**
     * indexNode - index a node if node not seen to this process
     * @param n - IASTNode
     */
    protected void indexNode(IASTNode n, OMPPragmaNode ePragma)
    {
        if (n==null)  return;
        if (!stmtMap_.containsKey(n)) {
            indexMap_.add(n);
            stmtMap_.put(n, new Integer(indexMap_.indexOf(n)));
            concurrencyMap_.put(n, new BitSet());
        }
        if (!phaseStmts_.contains(n))
            phaseStmts_.add(n);
        // Set up the exclusion map
        if (ePragma!=null && !exclusionMap_.contains(n))
            exclusionMap_.put(n, ePragma);
    }
    
    /**
     * getNodesConcurrentTo - get all nodes concurrent to given node
     * @param node - IASTNode
     * @return Set
     */
    public Set getNodesConcurrentTo(IASTNode node)
    {
        BitSet b = (BitSet)concurrencyMap_.get(node);
        if (b==null)  return null;    // stmt never registered - ind. called for wrong component
        
        HashSet ans = new HashSet();
        for(int i=b.nextSetBit(0); i>=0; i=b.nextSetBit(i+1)) 
           ans.add(indexMap_.get(i));
        return ans;
    }
    
    private boolean hasBarrierFreePathToSelf(OMPBasicBlock singleBlock)
    {
        BarrierPathDFS  dfs = new BarrierPathDFS(singleBlock);
        dfs.startWalking();
        
        return dfs.hasBarrierFreePath();
    }
    
    //-------------------------------------------------------------------------
    //  BarrierPathDFS - find barrier free path to pragma
    //-------------------------------------------------------------------------
    private class BarrierPathDFS extends OMPDFS
    {
        // find a barrier free path to this node
        protected OMPPragmaNode target_            = null;
        protected boolean       barrierFreeExists_ = false;
        
        public BarrierPathDFS(OMPBasicBlock block)
        {
            super(block);
            target_ = block.getPragmaContext();
        }
        
        public boolean hasBarrierFreePath()
        {
            return barrierFreeExists_;
        }
        
        /**
         * visit - visit method - what the user usually overrides
         * @param node - OMPCFGNode
         */
        public int visit(OMPCFGNode node)
        {
            if (node instanceof OMPPragmaNode) {
                OMPPragmaNode thisNode = (OMPPragmaNode)node;
                if (thisNode.isImplicitBarrier() || thisNode.getPragma().getOMPType()==PASTOMPPragma.OmpBarrier)
                    return SKIP;
                else if (thisNode==target_) {
                    barrierFreeExists_=true;
                    return ABORT;
                }
            }
            return CONTINUE;
        }
    }
    
    
}