mercredi 16 mars 2022

How to iterate through of all AST node in order to apply optimizitation?

I am making a toy compiler. The source language is an imperative language, the output language is C++ code with some optimization.

I have AST for inner representation.

I want to implement some optimization, first of all a basic loop unrolling optimization.

I have a base class, every statement class derived from it.

I know that I should use visitor pattern in order to make AST -> AST transofrmation.

So I want to make changes in every WhileStatement class. There can be inner WhileStatements, like this:

VarDeclaration
PrintStatement
CallFunction
WhileStatement
    IfStatement
        WhileStatement
        PrintStatement
PrintStatement

I can get the first level statements from bison. That is clear that I need to apply somehow the visitor pattern to process the inner statements.

First of all, I know the basic of visitor pattern, but I cannot apply it in my code properly. Good news, only WhileStatement, IfStatement and IfElseStatement can have (inner) list of statements

I share my code, I hope this time it will be enough to give me help.

So the base class:

class Statement
{
    public:
        virtual ~Statement();
        virtual void TypeCheck() = 0;
        virtual StatementType GetType() const = 0;
        virtual std::string GetCode() const = 0;
        virtual void accept(visitor& v) = 0;
};

WhileStatement class (IfStatement is almost looks like this):

class WhileStatement : public Statement
{
    public:
        WhileStatement(Expression* _exp, std::list<Statement*>* _statementList);
        ~WhileStatement();
        void TypeCheck();
        Expression* GetExpression() const;
        std::string GetCode() const;
        StatementType GetType() const;
        virtual void accept(visitor& v) override
        {
            v.visit(*this);
        }
    private:
        Expression* exp;
        std::list<Statement*>* statementList;
};

Please do not judge me because of this: std::list<Statement*>* bison can operate only with this type so this type is fix, I think I cannot use this std::list<Statement*> &statementList

My basic Loop unrolling optimization, it works well with the outer statements:

void LoopUnrollingOptimization(std::list<Statement*>* &outerStatements, int optimizationNumber)
{
    std::list<Statement*>::iterator it;
    for (it = outerStatements->begin(); it != outerStatements->end(); ++it)
    {
        Expression* exp = dynamic_cast<WhileStatement*>(*it)->GetExpression();
        std::list<Statement*>* statementList = dynamic_cast<WhileStatement*>(*it)->GetStatementList();
        int whileStatements = statementList->size();
            
        std::list<Statement*>::iterator it2 = statementList->begin();
        IfStatement* optimizedIf = new IfStatement(exp, "break;");
    
        statementList->push_back(optimizedIf);
        
        int size = statementList->size() * optimizationNumber;
        
        for (int i = 0; i < size; ++i)
        {
            if (size - 1 == i)
            {
                break;
            }
            statementList->push_back((*it2));
            ++it2;
        }
    }
}

I call this function in my grammar file (.y).

I implemented a visitor pattern:

class visitor
{
    public:
        virtual void visit(IfStatement& ifStatement) = 0;
        virtual void visit(WhileStatement& whileStatement) = 0;
        virtual void visit(DeclareVariableStatement& declare) = 0;
        virtual void visit(IfElseStatement& ifelsestmt) = 0;
};

class visitor_concrate : public visitor
{
  public:
    void visit(IfStatement& ifStatement)
    {
        // I do not know what should I provide here, maybe this:
        ifStatements.statementList; // I think it is wrong, because it is a void method.
    };

    void visit(WhileStatement& whileStatement) override
    {

    };

    void visit(DeclareVariableStatement& declare)
    {
        // nothing maybe, because this class do not have statementList
    };
};

It is clear to me, that my task is to process every node (does not matter the depth level of it).

But I got stuck with combine the visitor pattern with my loop unrolling function. So please tell me how to combine void LoopUnrollingOptimization(std::list<Statement*>* &outerStatements, int optimizationNumber) function with the visitor pattern in order to process every node at every depth.

As I said before there can be this kind of scenario:

DeclareVarStatement
PrintStatement
IfStatement
    IfElseStatement
        IfStatement
            IfStatement
                WhileStatement
DeclareVarStatement

In this case I have to make loop unrolling optimization in the innermost WhileStatement.

I appreciate help with coding, also with hints. But because of my lack of knowledge, I would be happy if someone could write me a working code or a pseudocode.

Thank you in advance!

Aucun commentaire:

Enregistrer un commentaire