main.c

//
// tiny subset of c compiler using LLVM-C
//

// prototype for std funcs
int strlen(char *s);
int isspace(char c);
int isdigit(char c);
int isalpha(char c);
int isalnum(char c);
int atoi(char *s);
int open(char *fname, int mode);
int read(int fd, char *buf, int mode);
int dprintf(int fd, char *fmt, ...);
int strncmp(char *p, char *s, long int len);
char *strcat(char *s0, char *s1);
char *strndup(char *s, int len);
void *realloc(void *addr, long int size);
void *calloc(int size, long int len);
void exit(int s);

// use void* for LLVM-C types not to parse headers
typedef void *LLVMTypeRef;
typedef void *LLVMValueRef;
typedef void *LLVMModuleRef;
typedef void *LLVMBuilderRef;
typedef void *LLVMContextRef;
typedef void *LLVMBasicBlockRef;

// value/prototypes for LLVM-C
int LLVMIntEQ = 32;
int LLVMIntNE = 33;
int LLVMIntUGT = 34;
int LLVMIntUGE = 35;
int LLVMIntULT = 36;
int LLVMIntULE = 37;
int LLVMIntSGT = 38;
int LLVMIntSGE = 39;
int LLVMIntSLT = 40;
int LLVMIntSLE = 41;

LLVMTypeRef LLVMInt1Type();
LLVMTypeRef LLVMInt8Type();
LLVMTypeRef LLVMInt32Type();
LLVMTypeRef LLVMInt64Type();
LLVMTypeRef LLVMVoidType();
LLVMTypeRef LLVMPointerType(LLVMTypeRef ty, int n);
LLVMTypeRef LLVMArrayType2(LLVMTypeRef ty, int size);
LLVMBuilderRef LLVMCreateBuilder();
LLVMModuleRef LLVMModuleCreateWithName(char *name);
LLVMValueRef LLVMFunctionType(LLVMTypeRef ty_ret, LLVMValueRef *ty_args,
                              int count_args, int is_varg);
LLVMValueRef LLVMAddFunction(LLVMModuleRef module, char *name, LLVMTypeRef ty);
LLVMContextRef LLVMGetModuleContext(LLVMModuleRef module);
LLVMTypeRef LLVMGetTypeByName2(LLVMContextRef cxt, char *name);
LLVMTypeRef LLVMGetNamedFunction(LLVMModuleRef module, char *name);
LLVMBasicBlockRef LLVMAppendBasicBlock(LLVMValueRef value, char *name);
void LLVMPositionBuilderAtEnd(LLVMBuilderRef bldr, LLVMBasicBlockRef blck);
LLVMBasicBlockRef LLVMGetInsertBlock(LLVMBuilderRef bldr);
LLVMValueRef LLVMGetBasicBlockParent(LLVMBasicBlockRef blck);
char *LLVMGetValueName(LLVMValueRef value);
LLVMValueRef LLVMConstInt(LLVMTypeRef ty, long int num, int signExtended);
LLVMValueRef LLVMConstNull(LLVMTypeRef ty);
LLVMValueRef LLVMBuildRet(LLVMBuilderRef bldr, LLVMValueRef returnValue);
LLVMValueRef LLVMBuildRetVoid(LLVMBuilderRef bldr);
LLVMValueRef LLVMBuildAdd(LLVMBuilderRef bldr, LLVMValueRef n0, LLVMValueRef n1,
                          char *name);
LLVMValueRef LLVMBuildSub(LLVMBuilderRef bldr, LLVMValueRef n0, LLVMValueRef n1,
                          char *name);
LLVMValueRef LLVMBuildMul(LLVMBuilderRef bldr, LLVMValueRef n0, LLVMValueRef n1,
                          char *name);
LLVMValueRef LLVMBuildSDiv(LLVMBuilderRef bldr, LLVMValueRef n0,
                           LLVMValueRef n1, char *name);
LLVMValueRef LLVMBuildSRem(LLVMBuilderRef bldr, LLVMValueRef n0,
                           LLVMValueRef n1, char *name);
LLVMValueRef LLVMBuildAlloca(LLVMBuilderRef bldr, LLVMTypeRef ty, char *name);
LLVMValueRef LLVMBuildArrayAlloca(LLVMBuilderRef bldr, LLVMTypeRef ty,
                                  LLVMValueRef size, char *name);
void LLVMSetInitializer(LLVMValueRef alc, LLVMValueRef value);
LLVMValueRef LLVMBuildStore(LLVMBuilderRef bldr, LLVMValueRef alc,
                            LLVMValueRef value);
LLVMValueRef LLVMBuildLoad2(LLVMBuilderRef bldr, LLVMTypeRef ty,
                            LLVMValueRef acl, char *name);
LLVMValueRef LLVMBuildCall2(LLVMBuilderRef bldr, LLVMTypeRef ty,
                            LLVMValueRef alc, LLVMValueRef *args, int len,
                            char *name);
LLVMValueRef LLVMGetParam(LLVMValueRef fn, int n);
LLVMValueRef LLVMAddGlobal(LLVMModuleRef mod, LLVMTypeRef ty, char *name);
LLVMValueRef LLVMBuildGlobalStringPtr(LLVMBuilderRef bldr, char *str,
                                      char *name);
LLVMValueRef LLVMBuildGEP2(LLVMBuilderRef bldr, LLVMTypeRef ty,
                           LLVMValueRef val, LLVMValueRef *indice, int len,
                           char *name);
LLVMValueRef LLVMBuildSExt(LLVMBuilderRef bldr, LLVMValueRef value,
                           LLVMTypeRef ty, char *name);
LLVMValueRef LLVMBuildZExt(LLVMBuilderRef bldr, LLVMValueRef value,
                           LLVMTypeRef ty, char *name);
LLVMValueRef LLVMBuildTrunc(LLVMBuilderRef bldr, LLVMValueRef value,
                            LLVMTypeRef ty, char *name);
LLVMValueRef LLVMBuildPtrToInt(LLVMBuilderRef bldr, LLVMValueRef value,
                               LLVMTypeRef ty, char *name);
LLVMTypeRef LLVMStructCreateNamed(LLVMContextRef contxt, char *name);
LLVMContextRef LLVMGetGlobalContext();
void LLVMStructSetBody(LLVMTypeRef ty, LLVMTypeRef *tylst, int len, int packed);
LLVMValueRef LLVMBuildICmp(LLVMBuilderRef bldr, int op, LLVMValueRef lhv,
                           LLVMValueRef rhv, char *name);
LLVMValueRef LLVMBuildPhi(LLVMBuilderRef bldr, LLVMTypeRef gnty, char *name);
LLVMValueRef LLVMAddIncoming(LLVMValueRef phi, LLVMValueRef value,
                             LLVMBasicBlockRef blk, int count);
LLVMValueRef LLVMBuildCondBr(LLVMBuilderRef bldr, LLVMValueRef ifblk,
                             LLVMBasicBlockRef thenblk,
                             LLVMBasicBlockRef elseblk);
LLVMValueRef LLVMBuildBr(LLVMBuilderRef bldr, LLVMBasicBlockRef dest);
LLVMBasicBlockRef LLVMCreateBasicBlockInContext(LLVMContextRef C, char *name);
void LLVMAppendExistingBasicBlock(LLVMValueRef Fn, LLVMBasicBlockRef BB);
char *LLVMPrintModuleToString(LLVMModuleRef module);

typedef enum _TK TK;
typedef enum _TY TY;
typedef enum _ND ND;

typedef struct _Lnk Lnk;
typedef struct _Token Token;
typedef struct _Node Node;
typedef struct _Type Type;
typedef struct _Obj Obj;
typedef struct _Scope Scope;

enum _TK {
    TK_CH = 100,
    TK_NUM,
    TK_IDENT,
    TK_LITERAL,
    TK_RESERVED,
    TK_EOF,
};

enum _ND {
    ND_EMPTY = 200,
    ND_LST,
    ND_CH,
    ND_NUM,
    ND_ADD,
    ND_SUB,
    ND_MUL,
    ND_DIV,
    ND_MOD,
    ND_VAR,
    ND_DCLR,
    ND_GL_DCLR,
    ND_ASSIGN,
    ND_FN_PROTO,
    ND_FN_DEF,
    ND_FN_CALL,
    ND_RETURN,
    ND_ADDR,
    ND_DEREF,
    ND_LITERAL,
    ND_PTR_CALC,
    ND_CAST,
    ND_STRUCTDEF,
    ND_DOT,
    ND_TYPEDEF,
    ND_SIZEOF,
    ND_EQ,
    ND_NOTEQ,
    ND_SGE,
    ND_SGT,
    ND_SLE,
    ND_SLT,
    ND_NOT,
    ND_LOGAND,
    ND_IF,
    ND_ELSE,
    ND_WHILE,
    ND_CONTINUE,
    ND_BREAK,
    ND_ENUMDEF,
};

enum _TY {
    TY_CH = 300,
    TY_INT,
    TY_LONG,
    TY_PTR,
    TY_VARG,
    TY_FUNC,
    TY_STRUCT,
    TY_ARRAY,
    TY_VOID,
    TY_ENUM,
};

// Lnk: circular bi-link list wih sentinel
struct _Lnk {
    char *nm;
    void *val;
    Lnk *prev;
    Lnk *next;
};

struct _Token {
    TK id;
    char *pos;
    int len;
    Token *prev;
};

struct _Type {
    TY id;
    char *tag;
    Type *to;
    Type *ret;
    Lnk *tylst;
    int num;
};

struct _Node {
    ND id;
    Node *lhn;
    Node *rhn;
    Lnk *nlst;
    char *str;
    long int value;
    Type *ty;
    Token *token;
    int is_varg;
};

// declared var and function both
struct _Obj {
    char *nm;
    Type *ty;
    LLVMTypeRef gnty;
    LLVMValueRef gnalc;
};

struct _Scope {
    char *fnm;
    Lnk *objlst;
    Lnk *tylst;
    Scope *next;
};

// local prototype
Type *consume_base_type();
Type *consume_type();
Node *nd_expr();
Node *nd_cast();
Node *nd_dclr(Type *ty, char *nm);
Node *nd_stmt();
Node *nd_stmtlst();
Type *type_get(char *tag, int is_err);
LLVMValueRef gn_dclr(Node *n);
LLVMValueRef gn_gl_dclr(Node *n);
LLVMValueRef gn_expr(Node *n);
LLVMValueRef gn_code(Node *n, LLVMBasicBlockRef cont, LLVMBasicBlockRef brk);

// global variables
void *NULL = 0;
char *input = 0;
char *pos = 0;
Lnk *keywords = 0;
Token *cur = 0;
Scope *scopelst = 0;
LLVMModuleRef module;
LLVMBuilderRef builder;

// utility function
char *scat(char *s0, char *s1) {
    s0 = realloc(s0, strlen(s0) + strlen(s1) + 1);
    return strcat(s0, s1);
}

int scmp(char *p, int len, char *s) {
    return len == strlen(s) && (strncmp(p, s, len) == 0);
}

void err_at(Token *t, char *msg, char *arg) {
    char *linestart = t->pos;
    char *lineend = t->pos;
    while (input < linestart && linestart[-1] != '\n') {
        linestart--;
    }
    while (*lineend && *lineend != '\n') {
        lineend++;
    }
    int linenum = 1;
    while (input < t->pos) {
        if (*input == '\n') {
            linenum++;
        }
        input++;
    }
    int column = t->pos - linestart + 1;
    dprintf(2, "%d:%d ", linenum, column);
    dprintf(2, "%s%s\n", msg, arg);
    dprintf(2, "%.*s\n", (int)(lineend - linestart), linestart);
    dprintf(2, "%*s^\n", column - 1, " ");
}

void exit_by0(int c, Token *t, char *msg, char *arg) {
    if (c && t) {
        err_at(t, msg, arg);
    } else if (c && !t) {
        dprintf(2, "%s%s\n", msg, arg);
    } else {
        return;
    }
    exit(1);
}

void exit_by(int c, char *msg, char *arg) { exit_by0(c, cur, msg, arg); }

char *read_file(char *path) {
    int fd = open(path, 0);
    exit_by(fd < 0, "Can not open file: ", path);
    int n = 0;
    int len = 0;
    char *buf = calloc(sizeof(char), len + 2);
    while ((n = read(fd, buf + len, len + 1))) {
        len += n;
        buf[len] = 0;
        buf = realloc(buf, (len + 1) * 2);
    }
    return buf;
}

char *norm_escapes(char *p) {
    char *ps = p;
    char *pp = p;
    while (*pp) {
        if (*pp == '\\') {
            pp++;
            if (*pp == 'n') {
                *pp = '\n';
            } else if (*pp == 't') {
                *pp = '\t';
            } else if (*pp == '\'') {
                *pp = '\'';
            } else if (*pp == '\\') {
                *pp = '\\';
            }
        }
        *(p++) = *(pp++);
    }
    *p = 0;
    return ps;
}

int lnk_len(Lnk *sentinel) {
    int len = 0;
    Lnk *lnk = sentinel->next;
    while (lnk != sentinel) {
        lnk = lnk->next;
        len++;
    }
    return len;
}

Lnk *lnk_init() {
    Lnk *lnk = calloc(sizeof(Lnk), 1);
    lnk->next = lnk->prev = lnk;
    return lnk;
}

Lnk *lnk_new(char *nm, void *val) {
    Lnk *lnk = calloc(sizeof(Lnk), 1);
    lnk->nm = nm;
    lnk->val = val;
    return lnk;
}

void lnk_add(Lnk *sentinel, char *nm, void *val) {
    Lnk *lnk = lnk_new(nm, val);
    lnk->prev = sentinel->prev;
    lnk->next = sentinel;
    sentinel->prev->next = lnk;
    sentinel->prev = lnk;
}

void lnk_push(Lnk *sentinel, char *nm, void *val) {
    Lnk *lnk = lnk_new(nm, val);
    lnk->prev = sentinel;
    lnk->next = sentinel->next;
    sentinel->next->prev = lnk;
    sentinel->next = lnk;
}

void *lnk_get(Lnk *sentinel, char *p, int len) {
    Lnk *lnk = sentinel->next;
    while (lnk != sentinel && !scmp(p, len, lnk->nm)) {
        lnk = lnk->next;
    }
    return lnk->val;
}

// register keywords for tokenizer
void kwd_init() {
    char *p = strndup("", 0);
    // concat lines not to parse divided long string literal
    p = scat(p, "char int long void "); // need last space
    p = scat(p, "return if else while continue break ");
    p = scat(p, "sizeof typedef struct enum ");
    p = scat(p, "-> == != <= >= -- ++ && || += -= %= /= *= ");
    p = scat(p, "...");
    keywords = lnk_init();
    while (*p) {
        char *ps = p;
        while (*p && *p != ' ') {
            p++;
        }
        char *kwd = strndup(ps, p - ps);
        lnk_add(keywords, kwd, kwd);
        p++;
    }
}

int is_kwd(char *p, int len) { return lnk_get(keywords, p, len) != NULL; }

Scope *scope_get(int is_global) {
    Scope *sc = scopelst;
    while (is_global && sc->next) {
        sc = sc->next;
    }
    return sc;
}

void scope_in(char *fnm) {
    Scope *nsc = calloc(sizeof(Scope), 1);
    nsc->objlst = lnk_init();
    nsc->tylst = lnk_init();
    nsc->fnm = fnm;
    nsc->next = scopelst;
    scopelst = nsc;
}

void scope_out() { scopelst = scopelst->next; }

void obj_push(char *nm, Type *ty, LLVMTypeRef gnty, LLVMValueRef gnalc,
              Lnk *lst) {
    Obj *obj = calloc(sizeof(Obj), 1);
    obj->nm = nm;
    obj->ty = ty;
    obj->gnty = gnty;
    obj->gnalc = gnalc;
    lnk_push(lst, nm, obj);
}

Obj *obj_get(char *nm) {
    Scope *sc = scopelst;
    Obj *obj = NULL;
    int len = strlen(nm);
    while (sc && !(obj = lnk_get(sc->objlst, nm, len))) {
        sc = sc->next;
    }
    exit_by(!obj, "Not found var/function: ", nm);
    return obj;
}

char *token_str(Token *t) {
    if (!t) {
        return "";
    }
    return strndup(t->pos, t->len);
}

Token *token_new(TK id, char *ps, char *p) {
    Token *t = calloc(sizeof(Token), 1);
    t->id = id;
    t->pos = ps;
    t->len = p - ps;
    return t;
}

void skip_ignorable() {
    while (*pos) {
        if (isspace(*pos) || *pos == '\n' || *pos == '\t') {
            pos++;
        } else if (scmp(pos, 2, "\\n")) {
            pos += 2;
        } else if (scmp(pos, 2, "//")) {
            while (*pos != '\n') {
                pos++;
            }
        } else if (scmp(pos, 2, "/*")) {
            while (!scmp(pos, 2, "*/")) {
                pos++;
            }
        } else {
            break;
        }
    }
}

Token *token_quoted(char *ps, char delim) {
    int escaped = 0;
    while (*pos != delim || escaped) {
        if (!escaped && *pos == '\\') {
            escaped = 1;
        } else {
            escaped = 0;
        }
        pos++;
    }
    if (delim == '\'') {
        return token_new(TK_CH, ps, pos++);
    }
    return token_new(TK_LITERAL, ps, pos++);
}

Token *token_next() {
    while (*pos) {
        skip_ignorable();
        char *ps = pos;

        if (*pos == '\'') {
            return token_quoted(++pos, '\'');
        } else if (*pos == '"') {
            return token_quoted(++pos, '"');
        } else if (isdigit(*pos)) {
            while (isdigit(*pos)) {
                pos++;
            }
            return token_new(TK_NUM, ps, pos);
        } else if (isalpha(*pos) || *pos == '_') {
            while (isalnum(*pos) || *pos == '_') {
                pos++;
            }
            if (is_kwd(ps, pos - ps)) {
                return token_new(TK_RESERVED, ps, pos);
            }
            return token_new(TK_IDENT, ps, pos);
        } else if (is_kwd(ps, 3)) {
            return token_new(TK_RESERVED, ps, pos += 3);
        } else if (is_kwd(ps, 2)) {
            return token_new(TK_RESERVED, ps, pos += 2);
        } else if (*pos) {
            return token_new(TK_RESERVED, ps, ++pos);
        }
        break;
    }
    return token_new(TK_EOF, pos - 1, pos - 1);
}

Token *token_is(char *s) {
    if (cur && cur->id == TK_RESERVED && scmp(cur->pos, cur->len, s)) {
        return cur;
    }
    return NULL;
}

Token *consume_any() {
    Token *t = cur;
    cur = token_next();
    cur->prev = t;
    return t;
}

Token *consume(char *s) {
    Token *t = NULL;
    if (cur && cur->id == TK_RESERVED && scmp(cur->pos, cur->len, s)) {
        t = consume_any();
    }
    return t;
}

Token *consume_id(TK id) {
    Token *t = NULL;
    if (cur && cur->id == id) {
        t = consume_any();
    }
    return t;
}

Token *expect(char *s) {
    Token *t = consume(s);
    exit_by(t == NULL, "Expected token: ", s);
    return t;
}

Token *expect_num() {
    Token *t = consume_id(TK_NUM);
    exit_by(t == NULL, "Expected number token", "");
    return t;
}

Token *expect_ident() {
    Token *t = consume_id(TK_IDENT);
    exit_by(t == NULL, "Expected ident token", "");
    return t;
}

Token *revert(int steps) {
    while (steps--) {
        pos = cur->pos;
        cur = cur->prev;
    }
    return cur;
}

Type *ty_new0(TY id, char *tag, Type *to, Type *ret) {
    Type *ty = calloc(sizeof(Type), 1);
    ty->id = id;
    ty->tag = tag;
    ty->to = to;
    ty->ret = ret;
    ty->tylst = lnk_init();
    return ty;
}

Type *ty_new_to(TY id, Type *to) { return ty_new0(id, "", to, NULL); }

Type *ty_new(TY id) { return ty_new_to(id, NULL); }

int eval(Node *n) {
    if (n->id == ND_ADD) {
        return eval(n->lhn) + eval(n->rhn);
    } else if (n->id == ND_SUB) {
        return eval(n->lhn) - eval(n->rhn);
    } else if (n->id == ND_MUL) {
        return eval(n->lhn) * eval(n->rhn);
    } else if (n->id == ND_DIV) {
        return eval(n->lhn) / eval(n->rhn);
    } else if (n->id == ND_NUM || n->id == ND_CH) {
        return n->value;
    }
    exit_by(1, "Not supported syntax for compile time", "");
    return 0;
}

Type *type_add(Type *ty) {
    if (!strlen(ty->tag)) {
        return ty;
    }
    Lnk *lnk = scopelst->tylst->next;
    while (lnk != scopelst->tylst) {
        Type *tty = lnk->val;
        if (scmp(ty->tag, strlen(ty->tag), tty->tag)) {
            tty->tylst = ty->tylst;
        }
        lnk = lnk->next;
    }
    lnk_push(scopelst->tylst, ty->tag, ty);
    return ty;
}

Type *consume_enum_type() {
    if (!consume("enum")) {
        return NULL;
    }
    char *tag = token_str(consume_id(TK_IDENT));
    if (!consume("{")) {
        revert(1 + (strlen(tag) > 0));
        return NULL;
    }
    Type *ty = ty_new0(TY_ENUM, tag, NULL, NULL);
    int num = 0;
    Token *t = NULL;
    while ((t = consume_id(TK_IDENT))) {
        char *tag = token_str(t);
        if (consume("=")) {
            num = atoi(token_str(expect_num()));
        }
        Type *ty0 = ty_new0(TY_INT, tag, NULL, NULL);
        ty0->num = num++;
        lnk_add(scopelst->tylst, tag, ty0);
        consume(",");
    }
    expect("}");
    return type_add(ty);
}

Type *consume_struct_type() {
    if (!consume("struct")) {
        return NULL;
    }
    char *tag = token_str(consume_id(TK_IDENT));
    if (!consume("{")) {
        revert(1 + (strlen(tag) > 0));
        return NULL;
    }
    Type *ty = ty_new0(TY_STRUCT, tag, NULL, NULL);
    Type *tyelm = NULL;
    int i = 0;
    while ((tyelm = consume_type())) {
        char *tagelm = token_str(expect_ident());
        tyelm->num = i++;
        lnk_add(ty->tylst, tagelm, tyelm);
        consume(";");
    }
    expect("}");
    return type_add(ty);
}

Type *consume_type() {
    Type *ty = NULL;

    if ((ty = consume_base_type())) {
    } else if (consume("struct")) {
        char *nm = token_str(expect_ident());
        if (!(ty = type_get(nm, 0))) {
            ty = ty_new0(TY_STRUCT, nm, NULL, NULL);
        }
    } else if (consume("enum")) {
        char *nm = token_str(expect_ident());
        if (!(ty = type_get(nm, 0))) {
            ty = ty_new0(TY_ENUM, nm, NULL, NULL);
        }
    } else {
        return NULL;
    }
    while (consume("*")) {
        ty = ty_new_to(TY_PTR, ty);
    }
    return ty;
}

Type *expect_type() {
    Type *ty = consume_type();
    exit_by(!ty, "Need type name", "");
    return ty;
}

Type *consume_base_type() {
    Type *ty = NULL;
    if (consume("int")) {
        ty = ty_new(TY_INT);
    } else if (consume("long")) {
        expect("int");
        ty = ty_new(TY_LONG);
    } else if (consume("char")) {
        ty = ty_new(TY_CH);
    } else if (consume("void")) {
        ty = ty_new(TY_VOID);
    } else if (consume("...")) {
        return ty_new(TY_VARG);
    } else if (cur && cur->id == TK_IDENT) {
        // defined type in declaration, or in typedef tag
        if ((ty = type_get(token_str(cur), 0))) {
            consume_id(TK_IDENT);
        } else {
            return NULL;
        }
    }
    return ty;
}

int is_ptr_types(Type *ty) { return ty->id == TY_ARRAY || ty->id == TY_PTR; }

Node *nd_new0(ND id, char *str, int value, Type *ty, Node *lhn, Node *rhn) {
    Node *n = calloc(sizeof(Node), 1);
    n->id = id;
    n->lhn = lhn;
    n->rhn = rhn;
    n->nlst = lnk_init();
    n->str = str;
    n->value = value;
    n->token = cur->prev;
    if (ty) {
        n->ty = ty;
    } else {
        n->ty = ty_new(TY_INT);
    }
    return n;
}

Node *nd_new_ty(ND id, Type *ty, Node *lhn, Node *rhn) {
    return nd_new0(id, NULL, 0, ty, lhn, rhn);
}

Node *nd_new(ND id, Node *lhn, Node *rhn) {
    return nd_new_ty(id, NULL, lhn, rhn);
}

Node *nd_num(int i) {
    return nd_new0(ND_NUM, NULL, i, ty_new(TY_INT), NULL, NULL);
}

Node *cast_to(Node *n, Type *tty) { return nd_new_ty(ND_CAST, tty, NULL, n); }

Node *nd_new_cond(ND id, Node *lhn, Node *rhn) {
    if (lhn->ty->id == TY_PTR) {
        lhn = cast_to(lhn, ty_new(TY_LONG));
    }
    return nd_new_ty(id, lhn->ty, lhn, rhn);
}

Node *nd_new_assign(Node *lhn, Node *rhn) {
    if (lhn->ty->id != rhn->ty->id) {
        rhn = cast_to(rhn, lhn->ty);
    }
    return nd_new_ty(ND_ASSIGN, lhn->ty, lhn, rhn);
}

Node *nd_minus(ND id, Node *n) {
    if (id == ND_SUB) {
        return nd_new(ND_SUB, nd_num(0), n);
    }
    return n;
}

Node *nd_new_ops(ND id, Node *lhn, Node *rhn) {

    if (is_ptr_types(lhn->ty) && !is_ptr_types(rhn->ty)) {
        return nd_new_ty(ND_PTR_CALC, lhn->ty, lhn, nd_minus(id, rhn));

    } else if (!is_ptr_types(lhn->ty) && is_ptr_types(rhn->ty)) {
        return nd_new_ty(ND_PTR_CALC, lhn->ty, rhn, nd_minus(id, lhn));

    } else if (is_ptr_types(lhn->ty) && is_ptr_types(rhn->ty)) {
        exit_by(id != ND_SUB, "Invalid operation for pointers", "");
        Type *ty = ty_new(TY_LONG);
        return nd_new_ty(id, ty, cast_to(lhn, ty), cast_to(rhn, ty));

    } else if (lhn->ty->id < rhn->ty->id) {
        lhn = cast_to(lhn, rhn->ty);
    } else if (lhn->ty->id > rhn->ty->id) {
        rhn = cast_to(rhn, lhn->ty);
    } else {
        return nd_new(id, lhn, rhn);
    }
    return nd_new_ty(id, lhn->ty, lhn, rhn);
}

Node *nd_return_check(Type *tyret, Node *nfn) {
    Node *last = nfn->rhn->nlst->prev->val;
    if (!last || last->id != ND_RETURN) {
        exit_by(tyret->id != TY_VOID, "Missing return in: ", nfn->str);
        lnk_add(nfn->rhn->nlst, NULL, nd_new(ND_RETURN, NULL, NULL));
    }
    return nfn;
}

void nd_obj_add(char *nm, Type *ty, int is_global) {
    Scope *sc = scope_get(is_global);
    obj_push(nm, ty, NULL, NULL, sc->objlst);
}

Type *type_get(char *tag, int chk_err) {
    Scope *sc = scopelst;
    Type *ty = NULL;
    while (sc && !(ty = lnk_get(sc->tylst, tag, strlen(tag)))) {
        sc = sc->next;
    }
    exit_by(!ty && chk_err, "No such type defined: ", tag);
    return ty;
}

int type_size(Type *ty) {
    TY id = ty->id;
    if (id == TY_CH || id == TY_VOID) {
        return 1;
    } else if (id == TY_INT || id == TY_ENUM) {
        return 4;
    } else if (id == TY_LONG || id == TY_PTR) {
        return 8;
    } else if (id == TY_STRUCT) {
        int size = 0;
        Lnk *lnk = ty->tylst->next;
        while (lnk != ty->tylst) {
            size += type_size(((Type *)lnk->val));
            lnk = lnk->next;
        }
        return size;
    }
    exit_by(1, "Can not calc size of type", "");
    return 0;
}

Node *nd_primary() {
    Token *t = NULL;
    Node *n = NULL;
    if (consume("(")) {
        n = nd_expr();
        expect(")");
    } else if ((t = consume_id(TK_CH))) {
        char *s = norm_escapes(token_str(t));
        exit_by(strlen(s) != 1, "Invalid length for char type: ", s);
        n = nd_new0(ND_CH, NULL, s[0], ty_new(TY_CH), NULL, NULL);
    } else if ((t = consume_id(TK_NUM))) {
        n = nd_num(atoi(t->pos));
    } else if ((t = consume_id(TK_IDENT))) {
        char *nm = token_str(t);
        Type *ty = NULL;
        if ((ty = type_get(nm, 0))) {
            n = nd_num(ty->num);
        } else if (!token_is("(")) {
            Obj *obj = obj_get(nm);
            exit_by(obj->ty->id == TY_FUNC,
                    "Not support func type as value: ", nm);
            n = nd_new0(ND_VAR, nm, 0, obj->ty, NULL, NULL);
        } else {
            n = nd_new0(ND_VAR, nm, 0, ty, NULL, NULL);
        }
    } else if ((t = consume_id(TK_LITERAL))) {
        char *str = norm_escapes(token_str(t));
        Type *ty = ty_new_to(TY_PTR, ty_new(TY_CH));
        n = nd_new0(ND_LITERAL, str, 0, ty, NULL, NULL);
    } else {
        exit_by(1, "Invalid syntax", "");
    }
    return n;
}

Node *nd_dot(Node *n) {
    char *nm = token_str(expect_ident());
    Type *tyelm = lnk_get(n->ty->tylst, nm, strlen(nm));
    return nd_new0(ND_DOT, nm, tyelm->num, tyelm, n, NULL);
}

Node *nd_postfix() {
    Node *n = nd_primary();
    while (1) {
        if (consume(".")) {
            n = nd_dot(n);
        } else if (consume("->")) {
            n = nd_dot(nd_new_ty(ND_DEREF, n->ty->to, NULL, n));
        } else if (consume("[")) {
            n = nd_new_ty(ND_DEREF, n->ty->to, NULL,
                          nd_new_ops(ND_ADD, n, nd_expr()));
            expect("]");
        } else if (consume("--")) {
            n = nd_new_assign(n, nd_new_ops(ND_SUB, n, nd_num(1)));
            n = nd_new_ops(ND_ADD, n, nd_num(1));
        } else if (consume("++")) {
            n = nd_new_assign(n, nd_new_ops(ND_ADD, n, nd_num(1)));
            n = nd_new_ops(ND_SUB, n, nd_num(1));
        } else if (consume("(")) {
            n->id = ND_FN_CALL;
            n->rhn = nd_new(ND_LST, NULL, NULL);
            while (cur && !token_is(")")) {
                lnk_add(n->rhn->nlst, NULL, nd_expr());
                consume(",");
            }
            expect(")");

            Obj *obj = obj_get(n->str);
            exit_by(obj->ty->id != TY_FUNC,
                    "Not support value type as func: ", n->str);
            n->ty = obj->ty->ret;

        } else {
            return n;
        }
    }
    return n;
}

Node *nd_unary() {
    Node *n = NULL;
    if (consume("&")) {
        n = nd_cast();
        n = nd_new_ty(ND_ADDR, ty_new_to(TY_PTR, n->ty), NULL, n);
    } else if (consume("*")) {
        n = nd_cast();
        n = nd_new_ty(ND_DEREF, n->ty->to, NULL, n);
    } else if (consume("!")) {
        n = nd_new(ND_NOT, NULL, nd_cast());
    } else if (consume("+")) {
        n = nd_cast();
    } else if (consume("-")) {
        n = nd_new_ops(ND_MUL, nd_num(-1), nd_cast());
    } else if (consume("--")) {
        n = nd_unary();
        Node *nn = nd_new_ops(ND_SUB, n, nd_num(1));
        n = nd_new_assign(n, nn);
    } else if (consume("++")) {
        n = nd_unary();
        Node *nn = nd_new_ops(ND_ADD, n, nd_num(1));
        n = nd_new_assign(n, nn);
    } else if (consume("sizeof")) {
        expect("(");
        n = nd_num(type_size(expect_type()));
        expect(")");
    } else {
        return nd_postfix();
    }
    return n;
}

Node *nd_cast() {
    Type *ty = NULL;
    if (consume("(")) {
        if ((ty = consume_type())) {
            expect(")");
            return nd_new_ty(ND_CAST, ty, NULL, nd_cast());
        }
        revert(1);
    }
    return nd_unary();
}

Node *nd_mul() {
    Node *n = nd_cast();
    while (1) {
        if (consume("*")) {
            n = nd_new_ops(ND_MUL, n, nd_cast());
        } else if (consume("/")) {
            n = nd_new_ops(ND_DIV, n, nd_cast());
        } else if (consume("%")) {
            n = nd_new_ops(ND_MOD, n, nd_cast());
        } else {
            break;
        }
    }
    return n;
}

Node *nd_add() {
    Node *n = nd_mul();
    while (1) {
        if (consume("+")) {
            n = nd_new_ops(ND_ADD, n, nd_mul());
        } else if (consume("-")) {
            n = nd_new_ops(ND_SUB, n, nd_mul());
        } else {
            break;
        }
    }
    return n;
}

Node *nd_relational() {
    Node *n = nd_add();
    while (1) {
        if (consume(">=")) {
            n = nd_new(ND_SGE, n, nd_add());
        } else if (consume(">")) {
            n = nd_new(ND_SGT, n, nd_add());
        } else if (consume("<=")) {
            n = nd_new(ND_SLE, n, nd_add());
        } else if (consume("<")) {
            n = nd_new(ND_SLT, n, nd_add());
        } else {
            break;
        }
    }
    return n;
}

Node *nd_equal() {
    Node *n = nd_relational();
    while (1) {
        if (consume("==")) {
            n = nd_new(ND_EQ, n, nd_equal());
        } else if (consume("!=")) {
            n = nd_new(ND_NOTEQ, n, nd_equal());
        } else {
            break;
        }
    }
    return n;
}

Node *nd_logand() {
    Node *n = nd_equal();
    while (1) {
        if (consume("&&")) {
            n = nd_new(ND_LOGAND, n, nd_logand());
        } else {
            break;
        }
    }
    return n;
}

Node *nd_logor() {
    Node *n = nd_logand();
    while (1) {
        if (consume("||")) {
            n = nd_new(ND_NOT, NULL, n);
            Node *nn = nd_new(ND_NOT, NULL, nd_logor());
            n = nd_new(ND_NOT, NULL, nd_new(ND_LOGAND, n, nn));
        } else {
            break;
        }
    }
    return n;
}

Node *nd_assign() {
    Node *n = nd_logor();
    Node *nn = NULL;
    while (1) {
        if ((consume("="))) {
            n = nd_new_assign(n, nd_assign());
            continue;
        } else if (consume("+=")) {
            nn = nd_new_ops(ND_ADD, n, nd_assign());
        } else if (consume("-=")) {
            nn = nd_new_ops(ND_SUB, n, nd_assign());
        } else if (consume("*=")) {
            nn = nd_new_ops(ND_MUL, n, nd_assign());
        } else if (consume("/=")) {
            nn = nd_new_ops(ND_DIV, n, nd_assign());
        } else if (consume("%=")) {
            nn = nd_new_ops(ND_MOD, n, nd_assign());
        } else {
            break;
        }
        n = nd_new_assign(n, nn);
    }
    return n;
}

Node *nd_expr() { return nd_assign(); }

Node *nd_dclr(Type *ty, char *nm) {
    Node *n = NULL;
    if (consume("[")) {
        ty = ty_new_to(TY_ARRAY, ty);
        n = nd_add();
        expect("]");
    }
    ND id = ND_DCLR;
    if (!scopelst->next) {
        id = ND_GL_DCLR;
    }
    nd_obj_add(nm, ty, 0);
    return nd_new0(id, nm, 0, ty, n, NULL);
}

void nd_dclr_args(Node *n) {
    Lnk *lnk = n->nlst->next;
    while (lnk != n->nlst) {
        Node *arg = lnk->val;
        nd_obj_add(arg->str, arg->ty, 0);
        lnk = lnk->next;
    }
}

Node *nd_func_proto(Type *ret, char *fnm) {
    Node *n = NULL;
    Type *fnty = ty_new0(TY_FUNC, fnm, NULL, ret);
    n = nd_new0(ND_FN_PROTO, fnm, 0, fnty, NULL, nd_new(ND_LST, NULL, NULL));

    Type *ty = NULL;
    while ((cur->id != TK_EOF && !token_is(")") && (ty = consume_type()))) {
        if (ty->id == TY_VARG) {
            n->is_varg = 1;
            continue;
        }
        char *nm = token_str(expect_ident());
        lnk_add(n->rhn->nlst, nm, nd_dclr(ty, nm));
        lnk_add(fnty->tylst, NULL, ty);
        consume(",");
    }

    nd_obj_add(fnm, fnty, 1);
    return n;
}

Node *nd_funcdef(Type *ty, char *fnm) {
    Node *n = NULL;
    if (consume("(")) {
        scope_in(fnm);
        n = nd_func_proto(ty, fnm);
        expect(")");
        if (consume("{")) {
            n = nd_new0(ND_FN_DEF, fnm, 0, NULL, n, nd_stmtlst());
            expect("}");
            nd_return_check(ty, n);
            nd_dclr_args(n->lhn->rhn);
        } else {
            expect(";");
        }
        scope_out();
    }
    return n;
}

Node *nd_direct_declarator(Type *ty) {
    Node *n = NULL;
    char *nm = token_str(expect_ident());
    if ((n = nd_funcdef(ty, nm))) {
        return n;
    }
    if ((n = nd_dclr(ty, nm))) {
        if (consume("=")) {
            if (n->id == ND_GL_DCLR) {
                n->value = eval(nd_add());
            } else {
                n = nd_new(ND_ASSIGN, n, nd_assign());
            }
        }
        expect(";");
    }
    return n;
}

Node *nd_if_blck() {
    Node *n = NULL;
    if (consume("{")) {
        n = nd_stmtlst();
        expect("}");
    } else {
        n = nd_stmt();
    }
    return n;
}

Node *nd_if() {
    Node *n = NULL;
    expect("(");
    n = nd_new_cond(ND_IF, nd_expr(), nd_new(ND_ELSE, NULL, NULL));
    expect(")");
    n->rhn->lhn = nd_if_blck();
    if (consume("else")) {
        n->rhn->rhn = nd_if_blck();
    }
    return n;
}

Node *nd_while() {
    Node *n = NULL;
    expect("(");
    n = nd_new_cond(ND_WHILE, nd_expr(), NULL);
    expect(")");
    if (consume("{")) {
        n->rhn = nd_stmtlst();
        expect("}");
    } else {
        n->rhn = nd_stmt();
    }
    return n;
}

Node *nd_return() {
    Node *nn = NULL;
    if (!token_is(";")) {
        Obj *obj = obj_get(scopelst->fnm);
        nn = cast_to(nd_expr(), obj->ty->ret);
    }
    return nd_new(ND_RETURN, NULL, nn);
}

Node *nd_stmt() {
    Node *n = NULL;
    Type *ty = NULL;

    if (consume("typedef")) {
        ty = expect_type();
        char *nm = token_str(expect_ident());
        lnk_push(scopelst->tylst, nm, ty);
        return nd_new0(ND_TYPEDEF, nm, 0, ty, NULL, NULL);
    }

    if (consume("if")) {
        return nd_if();
    } else if (consume("while")) {
        return nd_while();
    }

    if ((ty = consume_struct_type())) {
        n = nd_new_ty(ND_STRUCTDEF, ty, NULL, NULL);
    } else if ((ty = consume_enum_type())) {
        n = nd_new_ty(ND_ENUMDEF, ty, NULL, NULL);
    } else if ((ty = consume_type())) {
        return nd_direct_declarator(ty);
    } else if (consume("continue")) {
        n = nd_new(ND_CONTINUE, NULL, NULL);
    } else if (consume("break")) {
        n = nd_new(ND_BREAK, NULL, NULL);
    } else if (consume("return")) {
        n = nd_return();
    } else if (consume(";")) {
        return nd_new(ND_EMPTY, NULL, NULL);
    } else if ((n = nd_assign())) {
    } else {
        return NULL;
    }
    expect(";");
    return n;
}

Node *nd_stmtlst() {
    Node *n = nd_new(ND_LST, NULL, NULL);
    while (cur->id != TK_EOF && !token_is("}")) {
        lnk_add(n->nlst, NULL, nd_stmt());
    }
    return n;
}

Node *nd_parse() {
    scope_in("");
    cur = token_next();
    Node *n = nd_stmtlst();
    scope_out();
    return n;
}

void gn_obj_add(char *nm, Type *ty, LLVMTypeRef gnty, LLVMValueRef gn_acl) {
    obj_push(nm, ty, gnty, gn_acl, scopelst->objlst);
}

LLVMTypeRef gn_type(Type *ty) {
    if (ty->id == TY_CH) {
        return LLVMInt8Type();
    } else if (ty->id == TY_INT) {
        return LLVMInt32Type();
    } else if (ty->id == TY_LONG) {
        return LLVMInt64Type();
    } else if (ty->id == TY_VOID) {
        return LLVMVoidType();
    } else if (ty->id == TY_PTR) {
        return LLVMPointerType(gn_type(ty->to), 0);
    } else if (ty->id == TY_ENUM) {
        return LLVMInt32Type();
    } else if (ty->id == TY_STRUCT) {
        LLVMContextRef cxt = LLVMGetModuleContext(module);
        LLVMTypeRef gnty = LLVMGetTypeByName2(cxt, ty->tag);
        if (gnty) {
            return gnty;
        }
        return LLVMStructCreateNamed(cxt, ty->tag);
    } else if (ty->id == TY_ARRAY) {
        return gn_type(ty->to);
    }
    exit_by(1, "Not supported type", "");
    return NULL;
}

LLVMValueRef gn_zero(Type *ty) { return LLVMConstNull(gn_type(ty)); }

LLVMValueRef gn_num(int i) { return LLVMConstInt(LLVMInt32Type(), i, 0); }

LLVMValueRef gn_cast(Node *n, Type *ty_to) {
    LLVMValueRef value = gn_expr(n);
    TY idf = n->ty->id;
    TY idt = ty_to->id;
    if (idf == TY_FUNC) {
        idf = n->ty->id;
    }
    if (idf == idt) {
        return value;
    } else if (idf == TY_PTR) {
        return LLVMBuildPtrToInt(builder, value, gn_type(ty_to), "cast_ptr");
    } else if (idf < idt) {
        return LLVMBuildSExt(builder, value, gn_type(ty_to), "cast_ex");
    }
    return LLVMBuildTrunc(builder, value, gn_type(ty_to), "cast_tr");
}

LLVMValueRef gn_lval(Node *n) {
    if (n->id == ND_DEREF) {
        return gn_expr(n->rhn);
    } else if (n->id == ND_DOT) {
        LLVMValueRef indice[2];
        indice[0] = gn_num(0);
        indice[1] = gn_num(n->value);
        return LLVMBuildGEP2(builder, gn_type(n->lhn->ty), gn_lval(n->lhn),
                             indice, 2, "lval_dot");
    } else if (n->id == ND_DCLR) {
        return gn_dclr(n);
    } else if (n->id == ND_GL_DCLR) {
        return gn_gl_dclr(n);
    }
    Obj *obj = obj_get(n->str);
    return obj->gnalc;
}

LLVMValueRef gn_logand(Node *n) {
    LLVMContextRef cxt = LLVMGetGlobalContext();
    LLVMBasicBlockRef cntblk = LLVMGetInsertBlock(builder);
    LLVMValueRef cntfunc = LLVMGetBasicBlockParent(cntblk);
    LLVMBasicBlockRef trueblk =
        LLVMCreateBasicBlockInContext(cxt, "logand_true");
    LLVMBasicBlockRef falseblk =
        LLVMCreateBasicBlockInContext(cxt, "logand_false");
    LLVMBasicBlockRef mergeblk =
        LLVMCreateBasicBlockInContext(cxt, "logand_merge");

    LLVMValueRef lhs = gn_expr(n->lhn);
    lhs = LLVMBuildICmp(builder, LLVMIntNE, lhs, gn_zero(n->lhn->ty),
                        "logand_cmp1");
    LLVMBuildCondBr(builder, lhs, trueblk, falseblk);

    LLVMAppendExistingBasicBlock(cntfunc, trueblk);
    LLVMPositionBuilderAtEnd(builder, trueblk);
    LLVMValueRef rhs = gn_expr(n->rhn);
    rhs = LLVMBuildICmp(builder, LLVMIntNE, rhs, gn_zero(n->rhn->ty),
                        "logand_cmp2");
    LLVMBuildBr(builder, mergeblk);
    trueblk = LLVMGetInsertBlock(builder);

    LLVMAppendExistingBasicBlock(cntfunc, falseblk);
    LLVMPositionBuilderAtEnd(builder, falseblk);
    LLVMValueRef falseval = LLVMConstInt(LLVMInt1Type(), 0, 0);
    LLVMBuildBr(builder, mergeblk);
    falseblk = LLVMGetInsertBlock(builder);

    LLVMAppendExistingBasicBlock(cntfunc, mergeblk);
    LLVMPositionBuilderAtEnd(builder, mergeblk);
    LLVMValueRef phi = LLVMBuildPhi(builder, LLVMInt1Type(), "logand");
    LLVMAddIncoming(phi, &rhs, &trueblk, 1);
    LLVMAddIncoming(phi, &falseval, &falseblk, 1);

    return LLVMBuildZExt(builder, phi, LLVMInt32Type(), "logand_cast_ex");
}

LLVMValueRef gn_cmp(int op, Node *n) {
    LLVMValueRef ret =
        LLVMBuildICmp(builder, op, gn_expr(n->lhn), gn_expr(n->rhn), "cmp");
    return LLVMBuildZExt(builder, ret, gn_type(n->ty), "cmp_cast_ex");
}

LLVMValueRef gn_fncall(Node *n) {
    Node *nargs = n->rhn;
    int len = lnk_len(nargs->nlst);
    LLVMValueRef args[len];

    int i = len;
    Lnk *aglst = nargs->nlst->prev;
    while (aglst != nargs->nlst) {
        args[--i] = gn_expr(aglst->val);
        aglst = aglst->prev;
    }

    Obj *obj = obj_get(n->str);
    char *nm = "call";
    if (obj->ty->ret->id == TY_VOID) {
        nm = "";
    }
    return LLVMBuildCall2(builder, obj->gnty, obj->gnalc, args, len, nm);
}

LLVMValueRef gn_var(Node *n) {
    Obj *obj = obj_get(n->str);
    if (obj->ty->id == TY_ARRAY) {
        LLVMValueRef index = gn_num(0);
        return LLVMBuildGEP2(builder, obj->gnty, obj->gnalc, &index, 1,
                             "array");
    }
    return LLVMBuildLoad2(builder, obj->gnty, obj->gnalc, n->str);
}

LLVMValueRef gn_expr(Node *n) {
    ND id = n->id;
    Node *lhn = n->lhn;
    Node *rhn = n->rhn;

    if (id == ND_PTR_CALC) {
        LLVMValueRef index = gn_expr(n->rhn);
        return LLVMBuildGEP2(builder, gn_type(n->lhn->ty->to), gn_expr(n->lhn),
                             &index, 1, "ptr_add");
    } else if (id == ND_NOT) {
        LLVMValueRef ret = LLVMBuildICmp(builder, LLVMIntEQ, gn_expr(rhn),
                                         gn_zero(rhn->ty), "not_cmp");
        return LLVMBuildZExt(builder, ret, LLVMInt32Type(), "not_cast_ex");
    } else if (id == ND_CAST) {
        return gn_cast(n->rhn, n->ty);
    } else if (id == ND_ADDR) {
        return gn_lval(n->rhn);
    } else if (id == ND_DEREF) {
        return LLVMBuildLoad2(builder, gn_type(n->ty), gn_expr(rhn), "deref");
    } else if (id == ND_ASSIGN) {
        LLVMValueRef value = gn_expr(rhn);
        LLVMBuildStore(builder, value, gn_lval(lhn));
        return value;
    } else if (id == ND_DOT) {
        return LLVMBuildLoad2(builder, gn_type(n->ty), gn_lval(n), "dot");
    } else if (id == ND_EQ) {
        return gn_cmp(LLVMIntEQ, n);
    } else if (id == ND_NOTEQ) {
        return gn_cmp(LLVMIntNE, n);
    } else if (id == ND_SGE) {
        return gn_cmp(LLVMIntSGE, n);
    } else if (id == ND_SGT) {
        return gn_cmp(LLVMIntSGT, n);
    } else if (id == ND_SLE) {
        return gn_cmp(LLVMIntSLE, n);
    } else if (id == ND_SLT) {
        return gn_cmp(LLVMIntSLT, n);
    } else if (id == ND_LOGAND) {
        return gn_logand(n);
    } else if (id == ND_ADD) {
        return LLVMBuildAdd(builder, gn_expr(lhn), gn_expr(rhn), "add");
    } else if (id == ND_SUB) {
        return LLVMBuildSub(builder, gn_expr(lhn), gn_expr(rhn), "minus");
    } else if (id == ND_MUL) {
        return LLVMBuildMul(builder, gn_expr(lhn), gn_expr(rhn), "mul");
    } else if (id == ND_DIV) {
        return LLVMBuildSDiv(builder, gn_expr(lhn), gn_expr(rhn), "div");
    } else if (id == ND_MOD) {
        return LLVMBuildSRem(builder, gn_expr(lhn), gn_expr(rhn), "rem");
    } else if (id == ND_FN_CALL) {
        return gn_fncall(n);
    } else if (id == ND_VAR) {
        return gn_var(n);
    } else if (id == ND_NUM || id == ND_CH) {
        return LLVMConstInt(gn_type(n->ty), n->value, 0);
    } else if (id == ND_LITERAL) {
        return LLVMBuildGlobalStringPtr(builder, n->str, "literal");
    }
    return NULL;
}

LLVMValueRef gn_gl_dclr(Node *n) {
    LLVMTypeRef gnty = gn_type(n->ty);
    LLVMValueRef gnalc = NULL;
    if (n->ty->id == TY_ARRAY) {
        int size = eval(n->lhn);
        gnalc = LLVMAddGlobal(module, LLVMArrayType2(gnty, size), n->str);
    } else {
        gnalc = LLVMAddGlobal(module, gnty, n->str);
    }
    if (n->value) {
        LLVMSetInitializer(gnalc, gn_num(n->value));
    } else {
        LLVMSetInitializer(gnalc, LLVMConstNull(gnty));
    }
    gn_obj_add(n->str, n->ty, gnty, gnalc);
    return gnalc;
}

LLVMValueRef gn_dclr(Node *n) {
    LLVMTypeRef gnty = gn_type(n->ty);
    LLVMValueRef gnalc = NULL;
    if (n->ty->id == TY_ARRAY) {
        LLVMValueRef gn_size = gn_expr(n->lhn);
        gnalc = LLVMBuildArrayAlloca(builder, gnty, gn_size, n->str);
    } else {
        gnalc = LLVMBuildAlloca(builder, gnty, n->str);
    }
    if (n->rhn) {
        LLVMBuildStore(builder, gn_expr(n->rhn), gnalc);
    }
    gn_obj_add(n->str, n->ty, gnty, gnalc);
    return gnalc;
}

LLVMValueRef gn_func_proto(Node *n) {
    char *nm = n->ty->tag;
    LLVMValueRef fn = LLVMGetNamedFunction(module, nm);
    if (fn) {
        return fn;
    }
    int len = lnk_len(n->ty->tylst);
    LLVMTypeRef args[len];

    int i = 0;
    Lnk *lnk = n->ty->tylst->next;
    while (i < len) {
        args[i++] = gn_type(lnk->val);
        lnk = lnk->next;
    }
    LLVMTypeRef gnty =
        LLVMFunctionType(gn_type(n->ty->ret), args, len, n->is_varg);
    fn = LLVMAddFunction(module, nm, gnty);
    gn_obj_add(nm, n->ty, gnty, fn);
    return fn;
}

LLVMValueRef gn_func_def(Node *n) {
    Node *lhn = n->lhn;
    LLVMValueRef fn = gn_func_proto(lhn);

    scope_in(lhn->ty->tag);
    LLVMBasicBlockRef block = LLVMAppendBasicBlock(fn, "block");
    LLVMPositionBuilderAtEnd(builder, block);

    int i = 0;
    Lnk *nlst = lhn->rhn->nlst->next;
    while (nlst != lhn->rhn->nlst) {
        LLVMBuildStore(builder, LLVMGetParam(fn, i++), gn_dclr(nlst->val));
        nlst = nlst->next;
    }

    gn_code(n->rhn, NULL, NULL);
    scope_out();
    return NULL;
}

LLVMValueRef gn_structdef(Node *n) {
    int len = lnk_len(n->ty->tylst);
    LLVMTypeRef gntylst[len];

    int i = 0;
    Lnk *lnk = n->ty->tylst->next;
    while (i < len) {
        gntylst[i++] = gn_type(lnk->val);
        lnk = lnk->next;
    }
    LLVMContextRef cxt = LLVMGetGlobalContext();
    LLVMTypeRef gnty = LLVMGetTypeByName2(cxt, n->ty->tag);
    if (!gnty) {
        gnty = LLVMStructCreateNamed(cxt, n->ty->tag);
    }
    LLVMStructSetBody(gnty, gntylst, len, 1);

    return NULL;
}

LLVMValueRef gn_if(Node *n, LLVMBasicBlockRef cont, LLVMBasicBlockRef brk) {
    Node *n_cond = n->lhn;
    Node *n_true = n->rhn->lhn;
    Node *n_false = n->rhn->rhn;
    if (!n_true && !n_false) {
        return NULL;
    }

    LLVMContextRef cxt = LLVMGetGlobalContext();
    LLVMBasicBlockRef cntblk = LLVMGetInsertBlock(builder);
    LLVMValueRef cntfunc = LLVMGetBasicBlockParent(cntblk);
    LLVMBasicBlockRef thenblk = LLVMCreateBasicBlockInContext(cxt, "if_then");
    LLVMBasicBlockRef elseblk = LLVMCreateBasicBlockInContext(cxt, "if_else");
    LLVMBasicBlockRef mergeblk = LLVMCreateBasicBlockInContext(cxt, "if_merge");

    LLVMValueRef lhs = gn_expr(n_cond);
    lhs = LLVMBuildICmp(builder, LLVMIntNE, lhs, gn_zero(n_cond->ty), "cmp");
    LLVMBuildCondBr(builder, lhs, thenblk, elseblk);

    LLVMAppendExistingBasicBlock(cntfunc, thenblk);
    LLVMPositionBuilderAtEnd(builder, thenblk);
    if (n_true) {
        gn_code(n_true, cont, brk);
    }
    LLVMBuildBr(builder, mergeblk);

    LLVMAppendExistingBasicBlock(cntfunc, elseblk);
    LLVMPositionBuilderAtEnd(builder, elseblk);
    if (n_false) {
        gn_code(n_false, cont, brk);
    }
    LLVMBuildBr(builder, mergeblk);

    LLVMAppendExistingBasicBlock(cntfunc, mergeblk);
    LLVMPositionBuilderAtEnd(builder, mergeblk);
    return NULL;
}

LLVMValueRef gn_while(Node *n) {
    Node *n_cond = n->lhn;
    Node *n_exec = n->rhn;
    if (!n_exec) {
        return NULL;
    }

    LLVMContextRef cxt = LLVMGetGlobalContext();
    LLVMBasicBlockRef cntblk = LLVMGetInsertBlock(builder);
    LLVMValueRef cntfunc = LLVMGetBasicBlockParent(cntblk);
    LLVMBasicBlockRef startblk =
        LLVMCreateBasicBlockInContext(cxt, "while_start");
    LLVMBasicBlockRef execblk =
        LLVMCreateBasicBlockInContext(cxt, "while_exec");
    LLVMBasicBlockRef exitblk =
        LLVMCreateBasicBlockInContext(cxt, "while_exit");

    LLVMBuildBr(builder, startblk);
    LLVMAppendExistingBasicBlock(cntfunc, startblk);
    LLVMPositionBuilderAtEnd(builder, startblk);

    LLVMValueRef lhs = gn_expr(n_cond);
    lhs = LLVMBuildICmp(builder, LLVMIntNE, lhs, gn_zero(n_cond->ty), "cmp");
    LLVMBuildCondBr(builder, lhs, execblk, exitblk);

    LLVMAppendExistingBasicBlock(cntfunc, execblk);
    LLVMPositionBuilderAtEnd(builder, execblk);
    gn_code(n_exec, startblk, exitblk);
    LLVMBuildBr(builder, startblk);

    LLVMAppendExistingBasicBlock(cntfunc, exitblk);
    LLVMPositionBuilderAtEnd(builder, exitblk);

    return NULL;
}

LLVMValueRef gn_return(Node *n) {
    if (n->rhn) {
        return LLVMBuildRet(builder, gn_expr(n->rhn));
    }
    return LLVMBuildRetVoid(builder);
}

LLVMValueRef gn_code(Node *n, LLVMBasicBlockRef cont, LLVMBasicBlockRef brk) {

    ND id = n->id;
    if (id == ND_TYPEDEF) {
    } else if (id == ND_DCLR) {
        return gn_dclr(n);
    } else if (id == ND_GL_DCLR) {
        return gn_gl_dclr(n);
    } else if (id == ND_FN_DEF) {
        return gn_func_def(n);
    } else if (id == ND_FN_PROTO) {
        return gn_func_proto(n);
    } else if (id == ND_IF) {
        return gn_if(n, cont, brk);
    } else if (id == ND_WHILE) {
        return gn_while(n);
    } else if (id == ND_RETURN) {
        return gn_return(n);
    } else if (id == ND_STRUCTDEF) {
        return gn_structdef(n);
    } else if (id == ND_LST) {
        Lnk *lnk = n->nlst->next;
        while (lnk != n->nlst) {
            gn_code(lnk->val, cont, brk);
            lnk = lnk->next;
        }
    } else if (id == ND_CONTINUE) {
        exit_by0(!cont, n->token, "Invalid use of continue", "");
        return LLVMBuildBr(builder, cont);
    } else if (id == ND_BREAK) {
        exit_by0(!brk, n->token, "Invalid use of break", "");
        return LLVMBuildBr(builder, brk);
    }
    return gn_expr(n);
}

void gn_ir(Node *n) {
    module = LLVMModuleCreateWithName("mymodyle");
    builder = LLVMCreateBuilder();
    scope_in("");
    gn_code(n, NULL, NULL);
    scope_out();
    dprintf(1, "%s", LLVMPrintModuleToString(module));
}

int main(int ac, char **av) {
    exit_by(ac < 2, "Need file name", "");
    input = pos = read_file(av[1]);
    kwd_init();

    gn_ir(nd_parse());
    return 0;
}