README.md

Course: Advanced compilation techniques tutorial 21-22 fall by Lian Li, at UCAS

File Structure:

.
├── assignment1
│   ├── judge	# auto judgement
│   ├── src		# source files
│   └── test	# test cases
├── assignment2
│   ├── judge
│   ├── src
│   └── test
└── assignment3
    ├── judge
    ├── src
    └── test

Environments:
- llvm-10.0.0
- docker on dockerhub
```
docker pull lczxxx123/llvm_10_hw:0.2
```

Assignment details:

Implement a basic interpreter based on Clang

Marking: 25 testcases are provided and each test case counts for 1 mark

Supported Language: We support a subset of C language constructs, as follows:

Type: int | char | void | *
Operator: * | + | - | * | / | < | > | == | = | [ ] 
Statements: IfStmt | WhileStmt | ForStmt | DeclStmt 
Expr : BinaryOperator | UnaryOperator | DeclRefExpr | CallExpr | CastExpr

We also need to support 4 external functions int GET(), void * MALLOC(int), void FREE (void *), void PRINT(int), the semantics of the 4 functions are self-explanatory.
A skeleton implementation ast-interpreter.tgz is provided, and you are welcome to make any changes to the implementation. The provided implementation is able to interpreter the simple program like :
```
extern int GET();
extern void * MALLOC(int);
extern void FREE(void *);
extern void PRINT(int);
int main() {
  int a;
  a = GET();
  PRINT(a);
}
```

We provide a more formal definition of the accepted language, as follows:

Program : DeclList
DeclList : Declaration DeclList | empty
Declaration : VarDecl FuncDecl
VarDecl : Type VarList;
Type : BaseType | QualType
BaseType : int | char | void
QualType : Type * 
VarList : ID, VarList | | ID[num], VarList | emtpy
FuncDecl : ExtFuncDecl | FuncDefinition
ExtFuncDecl : extern int GET(); | extern void * MALLOC(int); | extern void FREE(void *); | extern void PRINT(int);
FuncDefinition : Type ID (ParamList) { StmtList }
ParamList : Param, ParamList | empty
Param : Type ID
StmtList : Stmt, StmtList | empty
Stmt : IfStmt | WhileStmt | ForStmt | DeclStmt | CompoundStmt | CallStmt | AssignStmt | 
IfStmt : if (Expr) Stmt | if (Expr) Stmt else Stmt
WhileStmt : while (Expr) Stmt
DeclStmt : Type VarList;
AssignStmt : DeclRefExpr = Expr;
CallStmt : CallExpr;
CompoundStmt : { StmtList }
ForStmt : for ( Expr; Expr; Expr) Stmt
Expr : BinaryExpr | UnaryExpr | DeclRefExpr | CallExpr | CastExpr | ArrayExpr | DerefExpr | (Expr) | num
BinaryExpr : Expr BinOP Expr
BinaryOP : + | - | * | / | < | > | ==
UnaryExpr : - Expr
DeclRefExpr : ID
CallExpr : DeclRefExpr (ExprList)
ExprList : Expr, ExprList | empty
CastExpr : (Type) Expr
ArrayExpr : DeclRefExpr [Expr]
DerefExpr : * DeclRefExpr

Implement a basic Call Graph builder

output format：
```
${line} : ${func_name1}, ${func_name2} 
```
Note that ${line} is unique in output.

Given the test file:

#include <stdio.h>

int add(int a, int b) {
   return a+b;
}

int sub(int a, int b) {
   return a-b;
}

int foo(int a, int b, int (*a_fptr)(int, int)) {
    return a_fptr(a, b);
}


int main() {
    int (*a_fptr)(int, int) = add;
    int (*s_fptr)(int, int) = sub;
    int (*t_fptr)(int, int) = 0;

    char x;
    int op1, op2;
    fprintf(stderr, "Please input num1 +/- num2 \n");

    fscanf(stdin, "%d %c %d", &op1, &x, &op2);

    if (x == '+') {
       t_fptr = a_fptr;
    }

    if (x == '-') {
       t_fptr = s_fptr;
    }

    if (t_fptr != NULL) {
       unsigned result = foo(op1, op2, t_fptr);
       fprintf (stderr, "Result is %d \n", result);
    } else {
       fprintf (stderr, "Unrecoganised operation %c", x);
    }
    return 0;
}

The output should be:

12 : add, sub
23 : fprintf
25 : fscanf
36 : foo
37 : fprintf
39 : fprintf

Implement a flow-sensitive, field- and context-insensitive algorithm to compute the points-to set for each variable at every call instructions. And print the callee functions each distinct program point.
- The printed format should be:
```
${line} : ${func_name1}, ${func_name2}
```
  Here ${line} is unique in output.
- One approach is to extend the provided dataflow analysis framework as follows:
  - Implement your representation of points-to sets
  - Implement the transfer function for each instruction
  - Implement the MEET operator
  - Extend the control flow graph to be inter-procedural
  Note that we do not require the analysis to be context-sensitive or field-sensitive.
- Give the test file:
```
#include <stdlib.h>
struct fpstruct {
    int (*t_fptr)(int,int);
};
       
int clever(int x) {
    int (*a_fptr)(int, int) = plus;
    int (*s_fptr)(int, int) = minus;
    int op1=1, op2=2;
    struct fpstruct * t1 = malloc(sizeof (struct fpstruct));
    if (x == 3) {
        t1->t_fptr = a_fptr;  
    } else {
        t1->t_fptr = s_fptr;
    } 
    unsigned result = t1->t_fptr(op1, op2);
    return 0;
}
```
- Your output should be：
```
9 : malloc
15 : plus, minus
```

charj99/ucas-compile

README.md