Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1108 > unrolled thread

Having trouble converting composite variables to intermediate form

Back to article view | Back to comp.compilers

Contents

  Having trouble converting composite variables to intermediate form noitalmost <noitalmost@cox.net> - 2014-02-22 12:32 -0500
    Re: Having trouble converting composite variables to intermediate form Momchil Velikov <momchil.velikov@gmail.com> - 2014-02-28 08:27 -0800
    Re: Having trouble converting composite variables to intermediate form noitalmost <noitalmost@cox.net> - 2014-03-10 15:18 -0400

#1108 — Having trouble converting composite variables to intermediate form

Quick overview:
I've been working on a Pascal-like language called Wirl, which includes an ILL
called Mezzo.
WirlSrc --> WirlAST --> MezzoAST --> Tripl --> binary
                                        | --> CSrc
where MezzoAST can produce Tripl (i.e. 3-address code) or low-level C.
Currently, only the C target has been developed to any significant degree.
Mezzo syntax is like a low-level Pascal.

So as not to bore anyone with the details of Mezzo, I'll translate the problem
as going from Wirl to low-level C. That is, a subset of C with no typedefs,
structs, or unions. Also, only very simple expressions are allowed. It's not
as restrictive as 3-addr code, but close. In particular, built-up expressions
with parentheses aren't allowed.

The problem:
var :
    r : record
            n : int;
            a : array[3] of int;
         end;
    x : int;
end;

x := r.a[2] + 5;

The compiler is implemented in C++. Below are some relevant classes. Many
details have been omitted. For brevity, consider all members as public.

class TypeDef {
	// a data type
	string name();
};

class ArrayType : public TypeDef {
	TypeDef* elemType();
	Expr* elemCnt();  // element count
};

class AstNode {
	virtual void genMezzo(MezzoNode *parent);
};

class Assign : public AstNode {
	Expr* lhs();
	Expr* rhs();
};

class Expr : public AstNode {
	virtual MezzoExpr* genMezzoExpr(MezzoNode *parent);
	TypeDef* resultType();
};

class Ident : public Expr {
	VarDef* varDef();  // variable definition that we reference
	// result type is type of the variable
};

class Op : public Expr {
	char optype();
	Expr* lhs();  // left-hand side
	Expr* rhs();  // right-hand side
};

class RecAccess : public Expr {
	Expr* record();
	Ident* field();  // the field we want to access
	// result type is type of field
};

class ArrAccess : public Expr {
	Expr* array();
	Expr* idx();  // index
	// result type is array element type
};


After parsing, the Wirl AST fragment looks like:
Assign
  Ident x
  Op +
    RecAccess
      Ident r
      ArrAccess
        Ident a
        Num 2

The trouble arises in the Mezzo generation, which traverses the Wirl AST
through genMezzo(MezzoNode *parent), which adds Mezzo nodes to parent.

void Assign::genMezzo(MezzoNode *parent) {
	// in the current case, parent is the statement list belonging
	// to the Mezzo program node

	MezzoExpr *mlhs = lhs()->genMezzoExpr(parent);
	MezzoExpr *mrhs = rhs()->genMezzoExpr(parent);

	parent->addStmt( new MezzoAssign(mlhs, mrhs) );
}

MezzoNode* Op::genMezzoExpr(MezzoNode *parent) {
	MezzoExpr *mlhs = lhs()->genMezzoExpr(parent);
	MezzoExpr *mrhs = rhs()->genMezzoExpr(parent);

	return new MezzoOp('+', mlhs, mrhs);
}

MezzoNode* RecAccess::genMezzoExpr(MezzoNode *parent) {
	// Mezzo has no record type, so we have to use ptr access

	MezzoExpr *mrec = record()->genMezzoExpr(parent);
	MezzoExpr *mfield = field()->genMezzoExpr(parent);

	// have to return addr of field?
}

MezzoNode* ArrAccess::genMezzoExpr(MezzoNode *parent) {
	// Mezzo has array of fundamental types only
	// so sometimes, we could return a value
	// but if we have composite elem type, we have to return an address

	// In the current case, we have to return an address
	// because parent is a record

	// Help, help. I'm in a mess!
}

For brevity, I've omitted the checks for complicated expressions that require
generation of temporaries, sanity checks, and the like.

Using C syntax for the Mezzo code, and assuming 4-byte ints, it should
generate something like:
#define IntSz 4
#define T0 (IntSz)
#define T1 (4 * 4)
char r[T0 + T1];
int x;

int main {
  char *T2 = r;
  int T3 = IntSz;  /* offset of a from r */
  int T4 = IntSz * 2;  /* offset from a */
  int T5 = T3 + T4;  /* offset from r */
  char *T6 = T2 + T5;  /* addr we're looking for */
  T7 = (int*)T6;
  T8 = *T7;
  x = T8 + 5;

  return 0;
}

Now how can I make my compiler do that?
The trouble I'm having has to do with the cast (in this case to int*) and the
following dereference. I don't know where to put them to get the correct
result. My code works okay for situations like
var r : record x,y : int end;
var a : array[7] of float;
The problem is when there's a combination of arrays and records.

[toc] | [next] | [standalone]

#1123

On Saturday, February 22, 2014 7:32:01 PM UTC+2, noitalmost wrote:
>
> x := r.a[2] + 5;
>

> After parsing, the Wirl AST fragment looks like:
>
> Assign
>   Ident x
>   Op +
>     RecAccess
>       Ident r
>       ArrAccess
>         Ident a
>         Num 2

You have currently

RecAccess(r, ArrAccess(Ident(a), Num(2)))

Note, however, that the array is not `a`, it's `r.a`. The subtree
`ArrAccess(Ident(a), Num(2)) `is incorrect, because you don't have in fact
a variable named `a` of an array type.

Here the record access should take precedence over array access, i.e.
the AST should look like:

ArrAccess(RecAccess(r, Ident(a)), Num(2))

[toc] | [prev] | [next] | [standalone]

#1141

On Friday, February 28, 2014 11:27:00 AM Momchil Velikov wrote:
> On Saturday, February 22, 2014 7:32:01 PM UTC+2, noitalmost wrote:
> > x := r.a[2] + 5;
> >
> >
> > After parsing, the Wirl AST fragment looks like:
> >
> > Assign
> >
> >   Ident x
> >   Op +
> >
> >     RecAccess
> >
> >       Ident r
> >       ArrAccess
> >
> >         Ident a
> >         Num 2
>
> You have currently
>
> RecAccess(r, ArrAccess(Ident(a), Num(2)))
>
> Note, however, that the array is not `a`, it's `r.a`. The subtree
> `ArrAccess(Ident(a), Num(2)) `is incorrect, because you don't have in fact
> a variable named `a` of an array type.
>
> Here the record access should take precedence over array access, i.e.
> the AST should look like:
>
> ArrAccess(RecAccess(r, Ident(a)), Num(2))

Thanks. I eventually figured it out independently by working backward from the
C code I wanted to generate. The compiler can now handle arbitrary
combinations of records, arrays, and pointers. I spent a week jumping up and
down and dancing. Wirl has now graduated from toy to fun toy :)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web