nsz Git - libfirm/blob - include/libfirm/lowering.h

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Lowering of high level constructs.
   9  * @author  Michael Beck
  10  */
  11 #ifndef FIRM_LOWERING_H
  12 #define FIRM_LOWERING_H
  13
  14 #include <stddef.h>
  15
  16 #include "firm_types.h"
  17
  18 #include "begin.h"
  19
  20 /**
  21  * @defgroup ir_lowering  Lowering
  22  *
  23  * Lowering is the process of transforming a highlevel representation
  24  * (a representation closer to the sourcecode) into a lower-level representation
  25  * (something closer to the target machine).
  26  *
  27  * @{
  28  */
  29
  30 /**
  31  * Lower small CopyB nodes to Load/Store nodes, preserve medium-sized CopyB
  32  * nodes and replace large CopyBs by a call to memcpy, depending on the given
  33  * parameters.
  34  *
  35  * Small CopyB nodes (size <= max_small_size) are turned into a series of
  36  * loads and stores.
  37  * Medium-sized CopyB nodes (max_small_size < size < min_large_size) are
  38  * left untouched.
  39  * Large CopyB nodes (size >= min_large_size) are turned into a memcpy call.
  40  *
  41  * @param irg                 The graph to be lowered.
  42  * @param max_small_size      The maximum number of bytes for a CopyB node so
  43  *                            that it is still considered 'small'.
  44  * @param min_large_size      The minimum number of bytes for a CopyB node so
  45  *                            that it is regarded as 'large'.
  46  * @param allow_misalignments Backend can handle misaligned loads and stores.
  47  */
  48 FIRM_API void lower_CopyB(ir_graph *irg, unsigned max_small_size,
  49                           unsigned min_large_size, int allow_misalignments);
  50
  51 /**
  52  * Lowers all Switches (Cond nodes with non-boolean mode) depending on spare_size.
  53  * They will either remain the same or be converted into if-cascades.
  54  *
  55  * @param irg        The ir graph to be lowered.
  56  * @param small_switch  If switch has <= cases then change it to an if-cascade.
  57  * @param spare_size Allowed spare size for table switches in machine words.
  58  *                   (Default in edgfe: 128)
  59  * @param selector_mode mode which must be used for Switch selector
  60  */
  61 FIRM_API void lower_switch(ir_graph *irg, unsigned small_switch,
  62                            unsigned spare_size, ir_mode *selector_mode);
  63
  64 /**
  65  * Replaces SymConsts by a real constant if possible.
  66  * Replaces Sel nodes by address computation.  Also resolves array access.
  67  * Handle bit fields by added And/Or calculations.
  68  *
  69  * @param irg               the graph to lower
  70  *
  71  * @note: There is NO lowering ob objects oriented types. This is highly compiler
  72  *        and ABI specific and should be placed directly in the compiler.
  73  */
  74 FIRM_API void lower_highlevel_graph(ir_graph *irg);
  75
  76 /**
  77  * Creates an ir_graph pass for lower_highlevel_graph().
  78  *
  79  * @param name              the name of this pass or NULL
  80  *
  81  * @return  the newly created ir_graph pass
  82  */
  83 FIRM_API ir_graph_pass_t *lower_highlevel_graph_pass(const char *name);
  84
  85 /**
  86  * Replaces SymConsts by a real constant if possible.
  87  * Replaces Sel nodes by address computation.  Also resolves array access.
  88  * Handle bit fields by added And/Or calculations.
  89  * Lowers all graphs.
  90  *
  91  * @note There is NO lowering of objects oriented types. This is highly compiler
  92  *       and ABI specific and should be placed directly in the compiler.
  93  */
  94 FIRM_API void lower_highlevel(void);
  95
  96 /**
  97  * does the same as lower_highlevel for all nodes on the const code irg
  98  */
  99 FIRM_API void lower_const_code(void);
 100
 101 /**
 102  * Creates an ir_prog pass for lower_const_code().
 103  *
 104  * @param name     the name of this pass or NULL
 105  *
 106  * @return  the newly created ir_prog pass
 107  */
 108 FIRM_API ir_prog_pass_t *lower_const_code_pass(const char *name);
 109
 110 /**
 111  * Used as callback, whenever a lowerable mux is found. The return value
 112  * indicates, whether the mux should be lowered. This may be used, to lower
 113  * floating point muxes, while keeping mux nodes for integers, for example.
 114  *
 115  * @param mux  The mux node that may be lowered.
 116  * @return     A non-zero value indicates that the mux should be lowered.
 117  */
 118 typedef int lower_mux_callback(ir_node* mux);
 119
 120 /**
 121  * Lowers all mux nodes in the given graph. A callback function may be
 122  * given, to select the mux nodes to lower.
 123  *
 124  * @param irg      The graph to lower mux nodes in.
 125  * @param cb_func  The callback function for mux selection. Can be NULL,
 126  *                 to lower all mux nodes.
 127  */
 128 FIRM_API void lower_mux(ir_graph *irg, lower_mux_callback *cb_func);
 129
 130 /**
 131  * Creates an ir_graph pass for lower_mux().
 132  *
 133  * @param name     the name of this pass or NULL
 134  * @param cb_func  The callback function for mux selection. Can be NULL,
 135  *                 to lower all mux nodes.
 136  *
 137  * @return  the newly created ir_graph pass
 138  */
 139 FIRM_API ir_graph_pass_t *lower_mux_pass(const char *name,
 140                                          lower_mux_callback *cb_func);
 141
 142 /**
 143  * An intrinsic mapper function.
 144  *
 145  * @param node   the IR-node that will be mapped
 146  * @param ctx    a context
 147  *
 148  * @return  non-zero if the call was mapped
 149  */
 150 typedef int (*i_mapper_func)(ir_node *node, void *ctx);
 151
 152 /** kind of an instruction record
 153  * @see #i_record */
 154 enum ikind {
 155         INTRINSIC_CALL  = 0,  /**< the record represents an intrinsic call */
 156         INTRINSIC_INSTR       /**< the record represents an intrinsic instruction */
 157 };
 158
 159 /**
 160  * An intrinsic call record.
 161  */
 162 typedef struct i_call_record {
 163         enum ikind    kind;       /**< must be INTRINSIC_CALL */
 164         ir_entity     *i_ent;     /**< the entity representing an intrinsic call */
 165         i_mapper_func i_mapper;   /**< the mapper function to call */
 166         void          *ctx;       /**< mapper context */
 167         void          *link;      /**< used in the construction algorithm, must be NULL */
 168 } i_call_record;
 169
 170 /**
 171  * An intrinsic instruction record.
 172  */
 173 typedef struct i_instr_record {
 174         enum ikind    kind;       /**< must be INTRINSIC_INSTR */
 175         ir_op         *op;        /**< the opcode that must be mapped. */
 176         i_mapper_func i_mapper;   /**< the mapper function to call */
 177         void          *ctx;       /**< mapper context */
 178         void          *link;      /**< used in the construction algorithm, must be NULL */
 179 } i_instr_record;
 180
 181 /**
 182  * An intrinsic record.
 183  */
 184 typedef union i_record {
 185         enum ikind     kind;     /**< kind of record */
 186         i_call_record  i_call;   /**< used for call records */
 187         i_instr_record i_instr;  /**< used for isnstruction records */
 188 } i_record;
 189
 190 /**
 191  * Go through all graphs and map calls to intrinsic functions and instructions.
 192  *
 193  * Every call or instruction is reported to its mapper function,
 194  * which is responsible for rebuilding the graph.
 195  *
 196  * @param list             an array of intrinsic map records
 197  * @param length           the length of the array
 198  * @param part_block_used  set to true if part_block() must be using during lowering
 199  *
 200  * @return number of found intrinsics.
 201  */
 202 FIRM_API size_t lower_intrinsics(i_record *list, size_t length,
 203                                  int part_block_used);
 204
 205 /**
 206  * Creates an irprog pass for lower_intrinsics.
 207  *
 208  * @param name             the name of this pass or NULL
 209  * @param list             an array of intrinsic map records
 210  * @param length           the length of the array
 211  * @param part_block_used  set to true if part_block() must be using during lowering
 212  */
 213 FIRM_API ir_prog_pass_t *lower_intrinsics_pass(const char *name, i_record *list,
 214                                                size_t length, int part_block_used);
 215
 216 /**
 217  * A mapper for the integer/float absolute value: type abs(type v).
 218  * Replaces the call by a Abs node.
 219  *
 220  * @return always 1
 221  */
 222 FIRM_API int i_mapper_abs(ir_node *call, void *ctx);
 223
 224 /**
 225  * A mapper for the integer byte swap value: type bswap(type v).
 226  * Replaces the call by a builtin[ir_bk_bswap] node.
 227  *
 228  * @return always 1
 229  */
 230 FIRM_API int i_mapper_bswap(ir_node *call, void *ctx);
 231
 232 /**
 233  * A mapper for the floating point sqrt(v): floattype sqrt(floattype v);
 234  *
 235  * @return 1 if the sqrt call was removed, 0 else.
 236  */
 237 FIRM_API int i_mapper_sqrt(ir_node *call, void *ctx);
 238
 239 /**
 240  * A mapper for the floating point cbrt(v): floattype sqrt(floattype v);
 241  *
 242  * @return 1 if the cbrt call was removed, 0 else.
 243  */
 244 FIRM_API int i_mapper_cbrt(ir_node *call, void *ctx);
 245
 246 /**
 247  * A mapper for the floating point pow(a, b): floattype pow(floattype a, floattype b);
 248  *
 249  * @return 1 if the pow call was removed, 0 else.
 250  */
 251 FIRM_API int i_mapper_pow(ir_node *call, void *ctx);
 252
 253 /**
 254  * A mapper for the floating point exp(a): floattype exp(floattype a);
 255  *
 256  * @return 1 if the exp call was removed, 0 else.
 257  */
 258 FIRM_API int i_mapper_exp(ir_node *call, void *ctx);
 259
 260 /**
 261  * A mapper for the floating point exp2(a): floattype exp2(floattype a);
 262  *
 263  * @return 1 if the exp call was removed, 0 else.
 264  */
 265 FIRM_API int i_mapper_exp2(ir_node *call, void *ctx);
 266
 267 /**
 268  * A mapper for the floating point exp10(a): floattype exp10(floattype a);
 269  *
 270  * @return 1 if the exp call was removed, 0 else.
 271  */
 272 FIRM_API int i_mapper_exp10(ir_node *call, void *ctx);
 273
 274 /**
 275  * A mapper for the floating point log(a): floattype log(floattype a);
 276  *
 277  * @return 1 if the log call was removed, 0 else.
 278  */
 279 FIRM_API int i_mapper_log(ir_node *call, void *ctx);
 280
 281 /**
 282  * A mapper for the floating point log(a): floattype log(floattype a);
 283  *
 284  * @return 1 if the log call was removed, 0 else.
 285  */
 286 FIRM_API int i_mapper_log2(ir_node *call, void *ctx);
 287
 288 /**
 289  * A mapper for the floating point log(a): floattype log(floattype a);
 290  *
 291  * @return 1 if the log call was removed, 0 else.
 292  */
 293 FIRM_API int i_mapper_log10(ir_node *call, void *ctx);
 294
 295 /**
 296  * A mapper for the floating point sin(a): floattype sin(floattype a);
 297  *
 298  * @return 1 if the sin call was removed, 0 else.
 299  */
 300 FIRM_API int i_mapper_sin(ir_node *call, void *ctx);
 301
 302 /**
 303  * A mapper for the floating point sin(a): floattype cos(floattype a);
 304  *
 305  * @return 1 if the cos call was removed, 0 else.
 306  */
 307 FIRM_API int i_mapper_cos(ir_node *call, void *ctx);
 308
 309 /**
 310  * A mapper for the floating point tan(a): floattype tan(floattype a);
 311  *
 312  * @return 1 if the tan call was removed, 0 else.
 313  */
 314 FIRM_API int i_mapper_tan(ir_node *call, void *ctx);
 315
 316 /**
 317  * A mapper for the floating point asin(a): floattype asin(floattype a);
 318  *
 319  * @return 1 if the asin call was removed, 0 else.
 320  */
 321 FIRM_API int i_mapper_asin(ir_node *call, void *ctx);
 322
 323 /**
 324  * A mapper for the floating point acos(a): floattype acos(floattype a);
 325  *
 326  * @return 1 if the tan call was removed, 0 else.
 327  */
 328 FIRM_API int i_mapper_acos(ir_node *call, void *ctx);
 329
 330 /**
 331  * A mapper for the floating point atan(a): floattype atan(floattype a);
 332  *
 333  * @return 1 if the atan call was removed, 0 else.
 334  */
 335 FIRM_API int i_mapper_atan(ir_node *call, void *ctx);
 336
 337 /**
 338  * A mapper for the floating point sinh(a): floattype sinh(floattype a);
 339  *
 340  * @return 1 if the sinh call was removed, 0 else.
 341  */
 342 FIRM_API int i_mapper_sinh(ir_node *call, void *ctx);
 343
 344 /**
 345  * A mapper for the floating point cosh(a): floattype cosh(floattype a);
 346  *
 347  * @return 1 if the cosh call was removed, 0 else.
 348  */
 349 FIRM_API int i_mapper_cosh(ir_node *call, void *ctx);
 350
 351 /**
 352  * A mapper for the floating point tanh(a): floattype tanh(floattype a);
 353  *
 354  * @return 1 if the tanh call was removed, 0 else.
 355  */
 356 FIRM_API int i_mapper_tanh(ir_node *call, void *ctx);
 357
 358 /**
 359  * A mapper for the strcmp-Function: inttype strcmp(char pointer a, char pointer b);
 360  *
 361  * @return 1 if the strcmp call was removed, 0 else.
 362  */
 363 FIRM_API int i_mapper_strcmp(ir_node *call, void *ctx);
 364
 365 /**
 366  * A mapper for the strncmp-Function: inttype strncmp(char pointer a, char pointer b, inttype len);
 367  *
 368  * @return 1 if the strncmp call was removed, 0 else.
 369  */
 370 FIRM_API int i_mapper_strncmp(ir_node *call, void *ctx);
 371
 372 /**
 373  * A mapper for the strcpy-Function: char pointer strcpy(char pointer a, char pointer b);
 374  *
 375  * @return 1 if the strcpy call was removed, 0 else.
 376  */
 377 FIRM_API int i_mapper_strcpy(ir_node *call, void *ctx);
 378
 379 /**
 380  * A mapper for the strlen-Function: inttype strlen(char pointer a);
 381  *
 382  * @return 1 if the strlen call was removed, 0 else.
 383  */
 384 FIRM_API int i_mapper_strlen(ir_node *call, void *ctx);
 385
 386 /**
 387  * A mapper for the memcpy-Function: void pointer memcpy(void pointer d, void pointer s, inttype c);
 388  *
 389  * @return 1 if the memcpy call was removed, 0 else.
 390  */
 391 FIRM_API int i_mapper_memcpy(ir_node *call, void *ctx);
 392
 393 /**
 394  * A mapper for the mempcpy-Function: void pointer mempcpy(void pointer d, void pointer s, inttype c);
 395  *
 396  * @return 1 if the mempcpy call was removed, 0 else.
 397  */
 398 FIRM_API int i_mapper_mempcpy(ir_node *call, void *ctx);
 399
 400 /**
 401  * A mapper for the memmove-Function: void pointer memmove(void pointer d, void pointer s, inttype c);
 402  *
 403  * @return 1 if the memmove call was removed, 0 else.
 404  */
 405 FIRM_API int i_mapper_memmove(ir_node *call, void *ctx);
 406
 407 /**
 408  * A mapper for the memset-Function: void pointer memset(void pointer d, inttype C, inttype len);
 409  *
 410  * @return 1 if the memset call was removed, 0 else.
 411  */
 412 FIRM_API int i_mapper_memset(ir_node *call, void *ctx);
 413
 414 /**
 415  * A mapper for the strncmp-Function: inttype memcmp(void pointer a, void pointer b, inttype len);
 416  *
 417  * @return 1 if the strncmp call was removed, 0 else.
 418  */
 419 FIRM_API int i_mapper_memcmp(ir_node *call, void *ctx);
 420
 421 /**
 422  * A mapper for the alloca() function: pointer alloca(inttype size)
 423  * Replaces the call by a Alloca(stack_alloc) node.
 424  *
 425  * @return always 1
 426  */
 427 FIRM_API int i_mapper_alloca(ir_node *call, void *ctx);
 428
 429 /**
 430  * A runtime routine description.
 431  */
 432 typedef struct runtime_rt {
 433         ir_entity *ent;            /**< The entity representing the runtime routine. */
 434         ir_mode   *mode;           /**< The operation mode of the mapped instruction. */
 435         ir_mode   *res_mode;       /**< The result mode of the mapped instruction or NULL. */
 436         long      mem_proj_nr;     /**< if >= 0, create a memory ProjM() */
 437         long      regular_proj_nr; /**< if >= 0, create a regular ProjX() */
 438         long      exc_proj_nr;     /**< if >= 0, create a exception ProjX() */
 439         long      res_proj_nr;     /**< if >= 0, first result projection number */
 440 } runtime_rt;
 441
 442 /**
 443  * A mapper for mapping unsupported instructions to runtime calls.
 444  * Maps a op(arg_0, ..., arg_n) into a call to a runtime function
 445  * rt(arg_0, ..., arg_n).
 446  *
 447  * The mapping is only done, if the modes of all arguments matches the
 448  * modes of rt's argument.
 449  * Further, if op has a memory input, the generated Call uses it, else
 450  * it gets a NoMem.
 451  * The pinned state of the Call will be set to the pinned state of op.
 452  *
 453  * Note that i_mapper_RuntimeCall() must be used with a i_instr_record.
 454  *
 455  * @return 1 if an op was mapped, 0 else
 456  *
 457  * Some examples:
 458  *
 459  * - Maps signed Div nodes to calls to rt_Div():
 460    @code
 461   runtime_rt rt_Div = {
 462     ent("int rt_Div(int, int)"),
 463     mode_T,
 464     mode_Is,
 465     pn_Div_M,
 466     pn_Div_X_regular,
 467     pn_Div_X_except,
 468     pn_Div_M,
 469     pn_Div_res
 470   };
 471   i_instr_record map_Div = {
 472     INTRINSIC_INSTR,
 473     op_Div,
 474     i_mapper_RuntimeCall,
 475     &rt_Div,
 476     NULL
 477   };
 478   @endcode
 479  *
 480  * - Maps ConvD(F) to calls to rt_Float2Div():
 481   @code
 482   runtime_rt rt_Float2Double = {
 483     ent("double rt_Float2Div(float)"),
 484     get_type_mode("double"),
 485     NULL,
 486     -1,
 487     -1,
 488     -1,
 489     -1,
 490     -1
 491   };
 492   i_instr_record map_Float2Double = {
 493     INTRINSIC_INSTR,
 494     op_Conv,
 495     i_mapper_RuntimeCall,
 496     &rt_Float2Double,
 497     NULL
 498   };
 499   @endcode
 500  */
 501 FIRM_API int i_mapper_RuntimeCall(ir_node *node, runtime_rt *rt);
 502
 503 /** @} */
 504
 505 #include "end.h"
 506
 507 #endif