linearize.h

   1 #ifndef LINEARIZE_H
   2 #define LINEARIZE_H
   3
   4 #include "lib.h"
   5 #include "token.h"
   6 #include "parse.h"
   7 #include "symbol.h"
   8
   9 struct instruction;
  10 struct pseudo_ptr_list;
  11
  12 enum pseudo_type {
  13         PSEUDO_VOID,
  14         PSEUDO_REG,
  15         PSEUDO_SYM,
  16         PSEUDO_VAL,
  17         PSEUDO_ARG,
  18 };
  19
  20 struct pseudo {
  21         int nr;
  22         unsigned int usage:24,
  23                      type:8;
  24         struct pseudo_ptr_list *users;
  25         union {
  26                 struct symbol *sym;
  27                 struct instruction *def;
  28                 long long value;
  29         };
  30 };
  31
  32 extern struct pseudo void_pseudo;
  33
  34 #define VOID (&void_pseudo)
  35
  36 struct multijmp {
  37         struct basic_block *target;
  38         int begin, end;
  39 };
  40
  41 struct phi {
  42         struct basic_block *source;
  43         pseudo_t pseudo;
  44 };
  45
  46 struct instruction {
  47         struct symbol *type;
  48         struct basic_block *bb;
  49         int opcode;
  50         union {
  51                 pseudo_t target;
  52                 pseudo_t cond;          /* for branch and switch */
  53         };
  54         union {
  55                 struct /* branch */ {
  56                         struct basic_block *bb_true, *bb_false;
  57                 };
  58                 struct /* switch */ {
  59                         struct multijmp_list *multijmp_list;
  60                 };
  61                 struct /* phi_node */ {
  62                         struct phi_list *phi_list;
  63                 };
  64                 struct /* unops */ {
  65                         struct symbol *orig_type;       /* casts */
  66                         pseudo_t src;
  67                         unsigned int offset;            /* memops */
  68                 };
  69                 struct /* binops */ {
  70                         pseudo_t src1, src2;
  71                 };
  72                 struct /* slice */ {
  73                         pseudo_t base;
  74                         unsigned from, len;
  75                 };
  76                 struct /* multijump */ {
  77                         int begin, end;
  78                 };
  79                 struct /* setval */ {
  80                         struct expression *val;
  81                         struct symbol *symbol;
  82                 };
  83                 struct /* call */ {
  84                         pseudo_t func;
  85                         struct pseudo_list *arguments;
  86                 };
  87                 struct /* context */ {
  88                         int increment;
  89                 };
  90         };
  91 };
  92
  93 enum opcode {
  94         OP_BADOP,
  95         /* Terminator */
  96         OP_TERMINATOR,
  97         OP_RET = OP_TERMINATOR,
  98         OP_BR,
  99         OP_SWITCH,
 100         OP_INVOKE,
 101         OP_COMPUTEDGOTO,
 102         OP_UNWIND,
 103         OP_TERMINATOR_END = OP_UNWIND,
 104
 105         /* Binary */
 106         OP_BINARY,
 107         OP_ADD = OP_BINARY,
 108         OP_SUB,
 109         OP_MUL,
 110         OP_DIV,
 111         OP_MOD,
 112         OP_SHL,
 113         OP_SHR,
 114         OP_SEL,
 115
 116         /* Logical */
 117         OP_AND,
 118         OP_OR,
 119         OP_XOR,
 120         OP_AND_BOOL,
 121         OP_OR_BOOL,
 122         OP_BINARY_END = OP_OR_BOOL,
 123
 124         /* Binary comparison */
 125         OP_BINCMP,
 126         OP_SET_EQ = OP_BINCMP,
 127         OP_SET_NE,
 128         OP_SET_LE,
 129         OP_SET_GE,
 130         OP_SET_LT,
 131         OP_SET_GT,
 132         OP_SET_B,
 133         OP_SET_A,
 134         OP_SET_BE,
 135         OP_SET_AE,
 136         OP_BINCMP_END = OP_SET_AE,
 137
 138         /* Uni */
 139         OP_NOT,
 140         OP_NEG,
 141
 142         /* Setcc - always in combination with a select or conditional branch */
 143         OP_SETCC,
 144
 145         /* Memory */
 146         OP_MALLOC,
 147         OP_FREE,
 148         OP_ALLOCA,
 149         OP_LOAD,
 150         OP_STORE,
 151         OP_SETVAL,
 152         OP_GET_ELEMENT_PTR,
 153
 154         /* Other */
 155         OP_PHI,
 156         OP_CAST,
 157         OP_CALL,
 158         OP_VANEXT,
 159         OP_VAARG,
 160         OP_SLICE,
 161         OP_SNOP,
 162         OP_LNOP,
 163         OP_NOP,
 164
 165         /* Sparse tagging (line numbers, context, whatever) */
 166         OP_CONTEXT,
 167 };
 168
 169 struct basic_block_list;
 170 struct instruction_list;
 171
 172 struct basic_block {
 173         struct position pos;
 174         unsigned long generation;
 175         int context;
 176         struct basic_block_list *parents; /* sources */
 177         struct basic_block_list *children; /* destinations */
 178         struct phi_list *phinodes;      /* phi-nodes that need this bb */
 179         struct instruction_list *insns; /* Linear list of instructions */
 180 };
 181
 182 static inline int is_branch_goto(struct instruction *br)
 183 {
 184         return br && br->opcode==OP_BR && (!br->bb_true || !br->bb_false);
 185 }
 186
 187 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
 188 {
 189         add_ptr_list((struct ptr_list **)list, bb);
 190 }
 191
 192 static inline void add_instruction(struct instruction_list **list, struct instruction *insn)
 193 {
 194         add_ptr_list((struct ptr_list **)list, insn);
 195 }
 196
 197 static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp)
 198 {
 199         add_ptr_list((struct ptr_list **)list, multijmp);
 200 }
 201
 202 static inline void add_phi(struct phi_list **list, struct phi *phi)
 203 {
 204         add_ptr_list((struct ptr_list **)list, phi);
 205 }
 206
 207 static inline void *add_pseudo(struct pseudo_list **list, struct pseudo *pseudo)
 208 {
 209         return add_ptr_list((struct ptr_list **)list, pseudo);
 210 }
 211
 212
 213 static inline int bb_terminated(struct basic_block *bb)
 214 {
 215         struct instruction *insn;
 216         if (!bb)
 217                 return 0;
 218         insn = last_instruction(bb->insns);
 219         return insn && insn->opcode >= OP_RET && insn->opcode <= OP_UNWIND;
 220 }
 221
 222 static inline int bb_reachable(struct basic_block *bb)
 223 {
 224         return bb != NULL;
 225 }
 226
 227 struct entrypoint {
 228         struct symbol *name;
 229         struct symbol_list *syms;
 230         struct symbol_list *accesses;
 231         struct instruction_list *switches;
 232         struct basic_block_list *bbs;
 233         struct basic_block *active;
 234         struct basic_block *entry;
 235 };
 236
 237 struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo);
 238 pseudo_t alloc_pseudo(struct instruction *def);
 239 pseudo_t value_pseudo(long long val);
 240
 241 struct entrypoint *linearize_symbol(struct symbol *sym);
 242 void show_entry(struct entrypoint *ep);
 243
 244 #endif /* LINEARIZE_H */
 245