[cfe-dev] Enhancing the DataFlowSolver in clang

[Simone Pellegrini]

On 02/12/2010 08:58 AM, Ted Kremenek wrote:
> Hi Simone,
>
> setTopValue() is probably misnamed; it is used by DataflowSolver to determine the "top" value when computing a merge at a confluence point.  It's not actually used anywhere else.
>
> If you want to specially initialize your bitvector values, the DataflowValues class does have an InitializeValues() method that is called by solver at the beginning of the analysis:
>
>    /// InitializeValues - Invoked by the solver to initialize state needed for
>    ///  dataflow analysis.  This method is usually specialized by subclasses.
>    void InitializeValues(const CFG&  cfg) {}
>
> The LiveVariables analysis doesn't actually use this method since the default bitvector values are fine for initial value, but in InitializeValues you can iterate over the CFG and set the values as you like.
>
> Would this work?
>    
Hi again,
I just found out that using InitializeValue() to initialize the state of 
the dataflow solver is not enough.

Let's for example consider an easy dataflow analysis: dominator trees. I 
need to create a bitvector where each position refers to a block of the 
CFG. Before starting the solver I need to initialize the values in the 
following way:

n0 (root node) = {0, 0, 0, n0, 0, ...}
N-n0 (remaining nodes) = {1,1,1,1..,1,1}

and this is what I am doing in the InitializeValue function:

/// Initializes the CFGBlock values for Dominators analysis i.e.:
/// * Dom(root) = {root}
/// * for each n in N - {root}, Dom(n) = N
void Dominators::InitializeValues(const CFG& cfg) {
   for(CFG::const_iterator I = cfg.begin(), E = cfg.end(); I != E; ++I) {
     Dominators::ValTy& D = getBlockDataMap()[*I];
     if(cfg.getEntry().getBlockID() == (*I)->getBlockID()) {
         D.resetValues(getAnalysisData());
         D((*I)->getBlockID(), getAnalysisData()) = IsDominator;
     } else
         D.setValues(getAnalysisData());
   }
}

My transfer function looks like this:

class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs> {
   Dominators::AnalysisDataTy& AD;
   Dominators::ValTy Dominance;
public:
   TransferFuncs(Dominators::AnalysisDataTy& ad) : AD(ad) { 
Dominance.resetValues(AD); }

   Dominators::ValTy& getVal() { return Dominance; }
   CFG& getCFG() { return AD.getCFG(); }

   void VisitTerminator(CFGBlock* B) {
     Dominance(B->getBlockID(), AD) = IsDominator; // add this as dominator
   }

   void SetTopValue(Dominators::ValTy& V) {  }
};

nothing difficult, but when I run the solver it gives me wrong results. :(
I investigated the problem and it seems that  the initial values I set 
in the initialize function are overwritten the first time the 
ProcessMerge() function is called by the DataflowSolver.

For what I understood from the code, the first time ProcessMerge() is 
called there is no edge data, therefore the last instruction in the 
function will always overwrite the existing block data with the one 
returned by the function TF.SetTopValue(), and in my case I don't have 
any TopValue to set.

To solve the problem I introduced a flag which track whether edge data 
exists. If not, the D.getBlockDataMap()[B] will not be overwritten.

What do you think?

cheers, Simone
> Ted
>
> On Feb 11, 2010, at 11:40 PM, Simone Pellegrini wrote:
>
>    
>> Hi all,
>>
>> I am currently trying to implement few simple dataflow analysis, namely
>> dominators and reaching definitions with the purpose to actually
>> understand how the clang's DataFlowSolver works.
>>
>> I got stuck with the dominator tree:
>> http://en.wikipedia.org/wiki/Dominator_(graph_theory)
>> The theory it's quite simple, but when I tried to implement it on the
>> solver I started to have some problems.
>>
>> The issue is that I need to set an initial state for each of the CFG
>> blocks, and more important I need to specify a different initial state
>> for each of the blocks (actually only the root node needs to have a
>> different initialization)
>>
>> For what I understand by reverse engineering the code, the method void
>> setTopValue(DominatorGraph::ValTy&  V) should be used to set the initial
>> state of a dataflow problem.
>>
>> However, in the dominators analysis I need to initialize the bitvectors
>> for each of the blocks with different values and in order to be able to
>> do that I need a different signature for the method which would be
>> something like:
>>
>> void SetTopValue(DominatorGraph::ValTy&  V, clang::CFGBlock const&  B){ }
>>
>> This modification requires only small changes in the DataFlowSolver and
>> implementation of dominators gets simpler.
>>
>> Is there any other way to have this kind of behaviour or it is really
>> missing? If you all agree with this change I can provide the patch!
>>
>> regards, S. Pellegrini
>> _______________________________________________
>> cfe-dev mailing list
>> cfe-dev at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>>      
>