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