nsz Git - libfirm/blob - ir/be/mips/mips_transform.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   The codegenrator (transform FIRM into mips FIRM
  23  * @author  Matthias Braun, Mehdi
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include <limits.h>
  29
  30 #include "irnode_t.h"
  31 #include "irgraph_t.h"
  32 #include "irmode_t.h"
  33 #include "irgmod.h"
  34 #include "iredges.h"
  35 #include "irvrfy.h"
  36 #include "ircons.h"
  37 #include "irprintf.h"
  38 #include "irop.h"
  39 #include "iropt_t.h"
  40 #include "debug.h"
  41 #include "error.h"
  42
  43 #include "../benode_t.h"
  44 #include "../beabi.h"
  45 #include "../besched.h"
  46 #include "../besched_t.h"
  47 #include "../beirg_t.h"
  48 #include "../betranshlp.h"
  49 #include "bearch_mips_t.h"
  50
  51 #include "mips_nodes_attr.h"
  52 #include "archop.h"
  53 #include "mips_transform.h"
  54 #include "mips_new_nodes.h"
  55 #include "mips_map_regs.h"
  56 #include "mips_util.h"
  57 #include "mips_emitter.h"
  58
  59 #include "gen_mips_regalloc_if.h"
  60
  61 /****************************************************************************************************
  62  *                  _        _                        __                           _   _
  63  *                 | |      | |                      / _|                         | | (_)
  64  *  _ __   ___   __| | ___  | |_ _ __ __ _ _ __  ___| |_ ___  _ __ _ __ ___   __ _| |_ _  ___  _ __
  65  * | '_ \ / _ \ / _` |/ _ \ | __| '__/ _` | '_ \/ __|  _/ _ \| '__| '_ ` _ \ / _` | __| |/ _ \| '_ \
  66  * | | | | (_) | (_| |  __/ | |_| | | (_| | | | \__ \ || (_) | |  | | | | | | (_| | |_| | (_) | | | |
  67  * |_| |_|\___/ \__,_|\___|  \__|_|  \__,_|_| |_|___/_| \___/|_|  |_| |_| |_|\__,_|\__|_|\___/|_| |_|
  68  *
  69  ****************************************************************************************************/
  70
  71 typedef ir_node *construct_binop_func(dbg_info *db, ir_graph *irg,
  72         ir_node *block, ir_node *left, ir_node *right);
  73
  74 static INLINE int mode_needs_gp_reg(ir_mode *mode) {
  75         return mode_is_int(mode) || mode_is_reference(mode);
  76 }
  77
  78 ir_node *mips_create_Immediate(long val)
  79 {
  80         ir_graph *irg   = current_ir_graph;
  81         ir_node  *block = get_irg_start_block(irg);
  82         const arch_register_t **slots;
  83         ir_node  *res;
  84
  85         assert(val >=  -32768 && val <= 32767);
  86         res      = new_rd_mips_Immediate(NULL, irg, block, MIPS_IMM_CONST, NULL,
  87                                          val);
  88         slots    = get_mips_slots(res);
  89         slots[0] = &mips_gp_regs[REG_GP_NOREG];
  90
  91         return res;
  92 }
  93
  94 ir_node* mips_create_zero(void)
  95 {
  96         ir_graph *irg   = current_ir_graph;
  97         ir_node  *block = get_irg_start_block(irg);
  98         ir_node  *zero  = new_rd_mips_zero(NULL, irg, block);
  99         const arch_register_t **slots = get_mips_slots(zero);
 100
 101         slots[0] = &mips_gp_regs[REG_ZERO];
 102
 103         return zero;
 104 }
 105
 106 static ir_node *try_create_Immediate(ir_node *node)
 107 {
 108         tarval   *tv;
 109         long      val;
 110         ir_mode  *mode;
 111
 112         if(!is_Const(node))
 113                 return NULL;
 114
 115         mode = get_irn_mode(node);
 116         if(!mode_needs_gp_reg(mode))
 117                 return NULL;
 118
 119         tv = get_Const_tarval(node);
 120         if(tarval_is_long(tv)) {
 121                 val = get_tarval_long(tv);
 122         } else {
 123                 ir_fprintf(stderr, "Optimisation Warning: tarval %+F is not a long?\n",
 124                            node);
 125                 return NULL;
 126         }
 127
 128         if(val < -32768 || val > 32767)
 129                 return NULL;
 130
 131         return mips_create_Immediate(val);
 132 }
 133
 134 static void create_binop_operands(ir_node **new_left, ir_node **new_right,
 135                                   ir_node *left, ir_node *right,
 136                                   int is_commutative)
 137 {
 138         *new_right = try_create_Immediate(right);
 139         if(*new_right != NULL) {
 140                 *new_left = be_transform_node(left);
 141                 return;
 142         }
 143         if(is_commutative) {
 144                 *new_right = try_create_Immediate(left);
 145                 if(*new_right != NULL) {
 146                         *new_left = be_transform_node(right);
 147                         return;
 148                 }
 149         }
 150
 151         *new_left  = be_transform_node(left);
 152         *new_right = be_transform_node(right);
 153 }
 154
 155 static ir_node *gen_binop(ir_node *node, ir_node *left, ir_node *right,
 156                           construct_binop_func func, int supports_immediate)
 157 {
 158         ir_graph *irg   = current_ir_graph;
 159         dbg_info *dbgi  = get_irn_dbg_info(node);
 160         ir_node  *block = be_transform_node(get_nodes_block(node));
 161         ir_node  *res;
 162         ir_node  *new_left, *new_right;
 163
 164         assert(mode_needs_gp_reg(get_irn_mode(node)));
 165
 166         if(supports_immediate) {
 167                 int is_commutative = is_op_commutative(get_irn_op(node));
 168                 create_binop_operands(&new_left, &new_right, left, right,
 169                                       is_commutative);
 170         } else {
 171                 new_left  = be_transform_node(left);
 172                 new_right = be_transform_node(right);
 173         }
 174
 175         res = func(dbgi, irg, block, new_left, new_right);
 176
 177         return res;
 178 }
 179
 180 static ir_node *gen_Add(ir_node *node)
 181 {
 182         /* TODO: match add(symconst, const) */
 183         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 184                          new_rd_mips_addu, 1);
 185 }
 186
 187 static ir_node *gen_Sub(ir_node *node)
 188 {
 189         return gen_binop(node, get_Sub_left(node), get_Sub_right(node),
 190                          new_rd_mips_addu, 0);
 191 }
 192
 193 static ir_node *gen_And(ir_node *node)
 194 {
 195         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 196                          new_rd_mips_and, 1);
 197 }
 198
 199 static ir_node *gen_Or(ir_node *node)
 200 {
 201         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 202                          new_rd_mips_or, 1);
 203 }
 204
 205 static ir_node *gen_Eor(ir_node *node)
 206 {
 207         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 208                          new_rd_mips_xor, 1);
 209 }
 210
 211 static ir_node *gen_Shl(ir_node *node)
 212 {
 213         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 214                          new_rd_mips_sll, 1);
 215 }
 216
 217 static ir_node *gen_Shr(ir_node *node)
 218 {
 219         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 220                          new_rd_mips_srl, 1);
 221 }
 222
 223 static ir_node *gen_Shrs(ir_node *node)
 224 {
 225         return gen_binop(node, get_Add_left(node), get_Add_right(node),
 226                          new_rd_mips_sra, 1);
 227 }
 228
 229 static ir_node *gen_Not(ir_node *node)
 230 {
 231         ir_graph *irg   = current_ir_graph;
 232         dbg_info *dbgi  = get_irn_dbg_info(node);
 233         ir_node  *block = be_transform_node(get_nodes_block(node));
 234         ir_node  *op    = get_Not_op(node);
 235         ir_node  *new_op;
 236         ir_node  *res;
 237         ir_node  *one;
 238
 239         /* we can transform not->or to nor */
 240         if(is_Or(op)) {
 241                 return gen_binop(op, get_Or_left(op), get_Or_right(op),
 242                                  new_rd_mips_nor, 1);
 243         }
 244
 245         /* construct (op < 1) */
 246         one    = mips_create_Immediate(1);
 247         new_op = be_transform_node(op);
 248         res    = new_rd_mips_sltu(dbgi, irg, block, new_op, one);
 249
 250         return res;
 251 }
 252
 253 static ir_node *gen_Minus(ir_node *node)
 254 {
 255         ir_graph *irg    = current_ir_graph;
 256         dbg_info *dbgi   = get_irn_dbg_info(node);
 257         ir_node  *block  = be_transform_node(get_nodes_block(node));
 258         ir_node  *op     = get_Minus_op(node);
 259         ir_node  *new_op = be_transform_node(op);
 260         ir_node  *res;
 261         ir_node  *zero;
 262
 263         /* construct (0 - op) */
 264         zero = mips_create_zero();
 265         res  = new_rd_mips_subu(dbgi, irg, block, zero, new_op);
 266
 267         return res;
 268 }
 269
 270 static ir_node *gen_Abs(ir_node *node)
 271 {
 272         ir_graph *irg    = current_ir_graph;
 273         dbg_info *dbgi   = get_irn_dbg_info(node);
 274         ir_node  *block  = be_transform_node(get_nodes_block(node));
 275         ir_node  *op     = get_Abs_op(node);
 276         ir_node  *new_op = be_transform_node(op);
 277         ir_node  *sra_const, *sra, *add, *xor;
 278
 279         /* TODO: support other bit sizes... */
 280         assert(get_mode_size_bits(get_irn_mode(node)) == 32);
 281         sra_const = mips_create_Immediate(31);
 282         sra       = new_rd_mips_sra(dbgi, irg, block, new_op, sra_const);
 283         add       = new_rd_mips_addu(dbgi, irg, block, new_op, sra);
 284         xor       = new_rd_mips_xor(dbgi, irg, block, sra, add);
 285
 286         return xor;
 287 }
 288
 289 static ir_node* gen_Const(ir_node *node)
 290 {
 291         ir_graph *irg   = current_ir_graph;
 292         dbg_info *dbgi  = get_irn_dbg_info(node);
 293         ir_node  *block = be_transform_node(get_nodes_block(node));
 294         tarval   *tv    = get_Const_tarval(node);
 295         ir_node  *upper_node;
 296         ir_node  *lower_node;
 297         ir_node  *or_const;
 298         unsigned long val, lower, upper;
 299
 300         if(tarval_is_long(tv)) {
 301                 val = get_tarval_long(tv);
 302         } else {
 303                 panic("Can't get value of tarval %+F", node);
 304         }
 305
 306         val = get_tarval_long(tv);
 307
 308         lower = val & 0xffff;
 309         upper = (val >> 16) & 0xffff;
 310         if(upper == 0) {
 311                 upper_node = mips_create_zero();
 312         } else {
 313                 upper_node = new_rd_mips_lui(dbgi, irg, block, MIPS_IMM_CONST, NULL,
 314                                              upper);
 315         }
 316
 317         if(lower == 0)
 318                 return upper_node;
 319
 320         or_const   = mips_create_Immediate(lower);
 321         lower_node = new_rd_mips_or(dbgi, irg, block, upper_node, or_const);
 322
 323         return lower_node;
 324 }
 325
 326 static ir_node* gen_SymConst(ir_node *node)
 327 {
 328         ir_graph *irg   = current_ir_graph;
 329         dbg_info *dbgi  = get_irn_dbg_info(node);
 330         ir_node  *block = be_transform_node(get_nodes_block(node));
 331         ir_entity *entity;
 332         const arch_register_t **slots;
 333         ir_node *lui, *or_const, *or;
 334
 335         if(get_SymConst_kind(node) != symconst_addr_ent) {
 336                 panic("Only address entity symconsts supported in mips backend");
 337         }
 338
 339         entity = get_SymConst_entity(node);
 340
 341         lui            = new_rd_mips_lui(dbgi, irg, block, MIPS_IMM_SYMCONST_HI,
 342                                          entity, 0);
 343         or_const       = new_rd_mips_Immediate(dbgi, irg, block,
 344                                                MIPS_IMM_SYMCONST_LO, entity, 0);
 345         or             = new_rd_mips_or(dbgi, irg, block, lui, or_const);
 346
 347         slots    = get_mips_slots(or_const);
 348         slots[0] = &mips_gp_regs[REG_GP_NOREG];
 349
 350         return or;
 351 }
 352
 353 typedef ir_node* (*gen_load_func) (dbg_info *dbg, ir_graph *irg,
 354                                    ir_node *block, ir_node *ptr, ir_node *mem,
 355                                    ir_entity *entity, long offset);
 356
 357 /**
 358  * Generates a mips node for a firm Load node
 359  */
 360 static ir_node *gen_Load(ir_node *node)
 361 {
 362         ir_graph *irg     = current_ir_graph;
 363         dbg_info *dbgi    = get_irn_dbg_info(node);
 364         ir_node  *block   = be_transform_node(get_nodes_block(node));
 365         ir_node  *mem     = get_Load_mem(node);
 366         ir_node  *new_mem = be_transform_node(mem);
 367         ir_node  *ptr     = get_Load_ptr(node);
 368         ir_node  *new_ptr = be_transform_node(ptr);
 369         ir_mode  *mode    = get_Load_mode(node);
 370         int       sign    = get_mode_sign(mode);
 371         ir_node  *res;
 372         gen_load_func func;
 373
 374         ASSERT_NO_FLOAT(mode);
 375         assert(mode_needs_gp_reg(mode));
 376
 377         /* TODO: make use of offset in ptrs */
 378
 379         switch(get_mode_size_bits(mode)) {
 380         case 32:
 381                 func = new_rd_mips_lw;
 382                 break;
 383         case 16:
 384                 func = sign ? new_rd_mips_lh : new_rd_mips_lhu;
 385                 break;
 386         case 8:
 387                 func = sign ? new_rd_mips_lb : new_rd_mips_lbu;
 388                 break;
 389         default:
 390                 panic("mips backend only support 32, 16, 8 bit loads");
 391         }
 392
 393         res = func(dbgi, irg, block, new_ptr, new_mem, NULL, 0);
 394         set_irn_pinned(res, get_irn_pinned(node));
 395
 396         return res;
 397 }
 398
 399 typedef ir_node* (*gen_store_func) (dbg_info *dbg, ir_graph *irg,
 400                                     ir_node *block, ir_node *ptr, ir_node *val,
 401                                     ir_node *mem, ir_entity *ent, long offset);
 402
 403 /**
 404  * Generates a mips node for a firm Store node
 405  */
 406 static ir_node *gen_Store(ir_node *node)
 407 {
 408         ir_graph    *irg     = current_ir_graph;
 409         dbg_info    *dbgi    = get_irn_dbg_info(node);
 410         ir_node     *block   = be_transform_node(get_nodes_block(node));
 411         ir_node     *mem     = get_Store_mem(node);
 412         ir_node     *new_mem = be_transform_node(mem);
 413         ir_node     *ptr     = get_Store_ptr(node);
 414         ir_node     *new_ptr = be_transform_node(ptr);
 415         ir_node     *val     = get_Store_value(node);
 416         ir_node     *new_val = be_transform_node(val);
 417         ir_mode     *mode    = get_irn_mode(val);
 418         gen_store_func func;
 419         ir_node     *res;
 420
 421         assert(mode_needs_gp_reg(mode));
 422
 423         switch(get_mode_size_bits(mode)) {
 424         case 32:
 425                 func = new_rd_mips_sw;
 426                 break;
 427         case 16:
 428                 func = new_rd_mips_sh;
 429                 break;
 430         case 8:
 431                 func = new_rd_mips_sb;
 432                 break;
 433         default:
 434                 panic("store only supported for 32, 16, 8 bit values in mips backend");
 435         }
 436
 437         res = func(dbgi, irg, block, new_ptr, new_val, new_mem, NULL, 0);
 438         set_irn_pinned(res, get_irn_pinned(node));
 439
 440         return res;
 441 }
 442
 443 static ir_node *gen_Proj_DivMod(ir_node *node)
 444 {
 445         ir_graph *irg     = current_ir_graph;
 446         dbg_info *dbgi    = get_irn_dbg_info(node);
 447         ir_node  *block   = be_transform_node(get_nodes_block(node));
 448         ir_node  *divmod  = get_Proj_pred(node);
 449         ir_node  *new_div = be_transform_node(divmod);
 450         long      pn      = get_Proj_proj(node);
 451         ir_node  *proj;
 452
 453         assert(is_mips_div(new_div) || is_mips_divu(new_div));
 454
 455         switch(get_irn_opcode(divmod)) {
 456         case iro_Div:
 457                 switch(pn) {
 458                 case pn_Div_M:
 459                         return new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 460                                            pn_mips_div_M);
 461                 case pn_Div_res:
 462                         proj = new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 463                                            pn_mips_div_lohi);
 464                         return new_rd_mips_mflo(dbgi, irg, block, proj);
 465                 default:
 466                         break;
 467                 }
 468         case iro_Mod:
 469                 switch(pn) {
 470                 case pn_Mod_M:
 471                         return new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 472                                            pn_mips_div_M);
 473                 case pn_Mod_res:
 474                         proj = new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 475                                            pn_mips_div_lohi);
 476                         return new_rd_mips_mfhi(dbgi, irg, block, proj);
 477                 default:
 478                         break;
 479                 }
 480
 481         case iro_DivMod:
 482                 switch(pn) {
 483                 case pn_Div_M:
 484                         return new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 485                                            pn_mips_div_M);
 486                 case pn_DivMod_res_div:
 487                         proj = new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 488                                            pn_mips_div_lohi);
 489                         return new_rd_mips_mflo(dbgi, irg, block, proj);
 490                 case pn_DivMod_res_mod:
 491                         proj = new_rd_Proj(dbgi, irg, block, new_div, mode_M,
 492                                            pn_mips_div_lohi);
 493                         return new_rd_mips_mfhi(dbgi, irg, block, proj);
 494                 default:
 495                         break;
 496                 }
 497         default:
 498                 break;
 499         }
 500
 501         panic("invalid proj attached to %+F", divmod);
 502 }
 503
 504 static ir_node *gen_Proj_Start(ir_node *node)
 505 {
 506         ir_graph *irg   = current_ir_graph;
 507         dbg_info *dbgi  = get_irn_dbg_info(node);
 508         ir_node  *block = be_transform_node(get_nodes_block(node));
 509         long      pn    = get_Proj_proj(node);
 510
 511         if(pn == pn_Start_X_initial_exec) {
 512                 /* we exchange the projx with a jump */
 513                 ir_node *jump = new_rd_Jmp(dbgi, irg, block);
 514                 return jump;
 515         }
 516         if(node == get_irg_anchor(irg, anchor_tls)) {
 517                 /* TODO... */
 518                 return be_duplicate_node(node);
 519         }
 520         return be_duplicate_node(node);
 521 }
 522
 523 static ir_node *gen_Proj(ir_node *node)
 524 {
 525         ir_graph *irg  = current_ir_graph;
 526         dbg_info *dbgi = get_irn_dbg_info(node);
 527         ir_node  *pred = get_Proj_pred(node);
 528
 529         switch(get_irn_opcode(pred)) {
 530         case iro_Load:
 531                 break;
 532         case iro_Store:
 533                 break;
 534         case iro_Div:
 535         case iro_Mod:
 536         case iro_DivMod:
 537                 return gen_Proj_DivMod(node);
 538
 539         case iro_Start:
 540                 return gen_Proj_Start(node);
 541
 542         default:
 543                 assert(get_irn_mode(node) != mode_T);
 544                 if(mode_needs_gp_reg(get_irn_mode(node))) {
 545                         ir_node *new_pred = be_transform_node(pred);
 546                         ir_node *block    = be_transform_node(get_nodes_block(node));
 547                         long     pn       = get_Proj_proj(node);
 548
 549                         return new_rd_Proj(dbgi, irg, block, new_pred, mode_Iu, pn);
 550                 }
 551                 break;
 552         }
 553
 554         return be_duplicate_node(node);
 555 }
 556
 557 static ir_node *gen_Phi(ir_node *node)
 558 {
 559         ir_graph *irg   = current_ir_graph;
 560         dbg_info *dbgi  = get_irn_dbg_info(node);
 561         ir_node  *block = be_transform_node(get_nodes_block(node));
 562         ir_mode  *mode  = get_irn_mode(node);
 563         ir_node  *phi;
 564
 565         if(mode_needs_gp_reg(mode)) {
 566                 assert(get_mode_size_bits(mode) <= 32);
 567                 mode = mode_Iu;
 568         }
 569
 570         /* phi nodes allow loops, so we use the old arguments for now
 571          * and fix this later */
 572         phi = new_ir_node(dbgi, irg, block, op_Phi, mode, get_irn_arity(node),
 573                           get_irn_in(node) + 1);
 574         copy_node_attr(node, phi);
 575         be_duplicate_deps(node, phi);
 576
 577         be_enqueue_preds(node);
 578
 579         return phi;
 580 }
 581
 582 #if 0
 583 static
 584 ir_node *gen_node_for_SwitchCond(mips_transform_env_t *env)
 585 {
 586         ir_node *selector = get_Cond_selector(env->irn);
 587         ir_mode *selector_mode = get_irn_mode(selector);
 588         ir_node *node = env->irn;
 589         dbg_info *dbg = env->dbg;
 590         ir_graph *irg = env->irg;
 591         ir_node *block = env->block;
 592         ir_node *sub, *sltu, *minval_const, *max_const, *switchjmp;
 593         ir_node *defaultproj, *defaultproj_succ;
 594         ir_node *beq, *sl;
 595         long pn, minval, maxval, defaultprojn;
 596         const ir_edge_t *edge;
 597         ir_node *zero, *two_const, *add, *la, *load, *proj;
 598         ir_mode *unsigned_mode;
 599         mips_attr_t *attr;
 600
 601         // mode_b conds are handled by gen_node_for_Proj
 602         if(get_mode_sort(selector_mode) != irms_int_number)
 603                 return env->irn;
 604
 605         assert(get_mode_size_bits(selector_mode) == 32);
 606
 607         defaultproj = NULL;
 608         defaultprojn = get_Cond_defaultProj(node);
 609
 610         // go over all projs to find min-&maxval of the switch
 611         minval = INT_MAX;
 612         maxval = INT_MIN;
 613         foreach_out_edge(node, edge) {
 614                 ir_node* proj = get_edge_src_irn(edge);
 615                 assert(is_Proj(proj) && "Only proj allowed at SwitchJmp");
 616
 617                 pn = get_Proj_proj(proj);
 618                 if(pn == defaultprojn) {
 619                         defaultproj = proj;
 620                         continue;
 621                 }
 622
 623                 if(pn < minval)
 624                         minval = pn;
 625                 if(pn > maxval)
 626                         maxval = pn;
 627         }
 628         assert(defaultproj != NULL);
 629
 630         // subtract minval from the switch value
 631
 632         if(minval != 0) {
 633                 minval_const = new_rd_Const(dbg, irg, block, selector_mode, new_tarval_from_long(minval, selector_mode));
 634                 minval_const = gen_node_for_Const(env, dbg, irg, block, minval_const);
 635                 sub = new_rd_mips_sub(dbg, irg, block, selector, minval_const);
 636         } else {
 637                 sub = selector;
 638         }
 639
 640         // compare if we're above maxval-minval or below zero.
 641         // we can do this with 1 compare because we use unsigned mode
 642         unsigned_mode = new_ir_mode(get_mode_name(selector_mode),
 643                         get_mode_sort(selector_mode), get_mode_size_bits(selector_mode),
 644                         0, get_mode_arithmetic(selector_mode), get_mode_modulo_shift(selector_mode));
 645
 646         max_const = new_rd_Const(dbg, irg, block, unsigned_mode, new_tarval_from_long(maxval - minval + 1, unsigned_mode));
 647         max_const = gen_node_for_Const(env, dbg, irg, block, max_const);
 648         sltu = new_rd_mips_slt(dbg, irg, block, sub, max_const);
 649
 650         zero = gen_zero_node(env, dbg, irg, block);
 651         beq = new_rd_mips_beq(dbg, irg, block, sltu, zero, mode_T);
 652
 653         // attach defaultproj to beq now
 654         set_irn_n(defaultproj, 0, beq);
 655         set_Proj_proj(defaultproj, 1);
 656
 657         two_const = new_rd_Const(dbg, irg, block, unsigned_mode, new_tarval_from_long(2, unsigned_mode));
 658         two_const = gen_node_for_Const(env, dbg, irg, block, two_const);
 659         sl = new_rd_mips_sl(dbg, irg, block, sub, two_const);
 660
 661         la = new_rd_mips_la(dbg, irg, block);
 662         add = new_rd_mips_addu(dbg, irg, block, sl, la);
 663         load = new_rd_mips_load_r(dbg, irg, block, new_rd_NoMem(irg), add, mode_T);
 664         attr = get_mips_attr(load);
 665         attr->modes.load_store_mode = mode_Iu;
 666         attr->tv = new_tarval_from_long(0, mode_Iu);
 667
 668         proj = new_rd_Proj(dbg, irg, block, load, mode_Iu, pn_Load_res);
 669
 670         switchjmp = new_rd_mips_SwitchJump(dbg, irg, block, proj, mode_T);
 671         attr = get_mips_attr(switchjmp);
 672         attr->switch_default_pn = defaultprojn;
 673
 674         edge = get_irn_out_edge_first(defaultproj);
 675         defaultproj_succ = get_edge_src_irn(edge);
 676         attr->symconst_id = new_id_from_str(mips_get_block_label(defaultproj_succ));
 677
 678         attr = get_mips_attr(la);
 679         attr->symconst_id = new_id_from_str(mips_get_jumptbl_label(switchjmp));
 680
 681         return switchjmp;
 682 }
 683 #endif
 684
 685 static ir_node *gen_Cond(ir_node *node)
 686 {
 687         ir_graph *irg       = current_ir_graph;
 688         dbg_info *dbgi      = get_irn_dbg_info(node);
 689         ir_node  *block     = get_nodes_block(node);
 690         ir_node  *sel_proj  = get_Cond_selector(node);
 691         ir_node  *cmp       = get_Proj_pred(sel_proj);
 692         ir_node  *left      = get_Cmp_left(cmp);
 693         ir_node  *new_left  = be_transform_node(left);
 694         ir_node  *right     = get_Cmp_right(cmp);
 695         ir_node  *new_right = be_transform_node(right);
 696         long      pnc       = get_Proj_proj(sel_proj);
 697         ir_node  *res;
 698         ir_node  *slt;
 699         ir_node  *zero;
 700
 701         /* TODO: use blez & co. when possible */
 702
 703         switch(pnc) {
 704         case pn_Cmp_False:
 705         case pn_Cmp_True:
 706         case pn_Cmp_Leg:
 707                 panic("mips backend can't handle unoptimized constant Cond");
 708
 709         case pn_Cmp_Eq:
 710                 res = new_rd_mips_beq(dbgi, irg, block, new_left, new_right);
 711                 break;
 712
 713         case pn_Cmp_Lt:
 714                 zero = mips_create_zero();
 715                 slt  = new_rd_mips_slt(dbgi, irg, block, new_left, new_right);
 716                 res  = new_rd_mips_bne(dbgi, irg, block, slt, zero);
 717                 break;
 718
 719         case pn_Cmp_Le:
 720                 zero = mips_create_zero();
 721                 slt  = new_rd_mips_slt(dbgi, irg, block, new_right, new_left);
 722                 res  = new_rd_mips_beq(dbgi, irg, block, slt, zero);
 723                 break;
 724
 725         case pn_Cmp_Gt:
 726                 zero = mips_create_zero();
 727                 slt  = new_rd_mips_slt(dbgi, irg, block, new_right, new_left);
 728                 res  = new_rd_mips_bne(dbgi, irg, block, slt, zero);
 729                 break;
 730
 731         case pn_Cmp_Ge:
 732                 zero = mips_create_zero();
 733                 slt  = new_rd_mips_slt(dbgi, irg, block, new_right, new_left);
 734                 res  = new_rd_mips_bne(dbgi, irg, block, slt, zero);
 735                 break;
 736
 737         case pn_Cmp_Lg:
 738                 res = new_rd_mips_bne(dbgi, irg, block, new_left, new_right);
 739                 break;
 740
 741         default:
 742                 panic("mips backend doesn't handle unordered compares yet");
 743         }
 744
 745         return res;
 746 }
 747
 748 static ir_node *gen_Conv(ir_node *node)
 749 {
 750         ir_graph *irg      = current_ir_graph;
 751         dbg_info *dbgi     = get_irn_dbg_info(node);
 752         ir_node  *block    = be_transform_node(get_nodes_block(node));
 753         ir_node  *op       = get_Conv_op(node);
 754         ir_node  *new_op   = be_transform_node(op);
 755         ir_mode  *src_mode = get_irn_mode(op);
 756         ir_mode  *dst_mode = get_irn_mode(node);
 757         int       src_size = get_mode_size_bits(src_mode);
 758         int       dst_size = get_mode_size_bits(dst_mode);
 759         ir_node  *res;
 760
 761         assert(mode_needs_gp_reg(src_mode));
 762         assert(mode_needs_gp_reg(dst_mode));
 763
 764         /* we only need to do something on upconvs */
 765         if(src_size >= dst_size) {
 766                 /* unnecessary conv */
 767                 return new_op;
 768         }
 769
 770         if(mode_is_signed(src_mode)) {
 771                 if(src_size == 8) {
 772                         res = new_rd_mips_seb(dbgi, irg, block, new_op);
 773                 } else if(src_size == 16) {
 774                         res = new_rd_mips_seh(dbgi, irg, block, new_op);
 775                 } else {
 776                         panic("invalid conv %+F", node);
 777                 }
 778         } else {
 779                 ir_node *and_const;
 780
 781                 if(src_size == 8) {
 782                         and_const = mips_create_Immediate(0xff);
 783                 } else if(src_size == 16) {
 784                         and_const = mips_create_Immediate(0xffff);
 785                 } else {
 786                         panic("invalid conv %+F", node);
 787                 }
 788                 res = new_rd_mips_and(dbgi, irg, block, new_op, and_const);
 789         }
 790
 791         return res;
 792 }
 793
 794 static ir_node *create_div(ir_node *node, ir_node *left, ir_node *right,
 795                            ir_mode *mode)
 796 {
 797         ir_graph *irg       = current_ir_graph;
 798         dbg_info *dbgi      = get_irn_dbg_info(node);
 799         ir_node  *block     = be_transform_node(get_nodes_block(node));
 800         ir_node  *new_left  = be_transform_node(left);
 801         ir_node  *new_right = be_transform_node(right);
 802         ir_node  *res;
 803
 804         if(mode_is_signed(mode)) {
 805                 res = new_rd_mips_div(dbgi, irg, block, new_left, new_right);
 806         } else {
 807                 res = new_rd_mips_divu(dbgi, irg, block, new_left, new_right);
 808         }
 809
 810         set_irn_pinned(res, get_irn_pinned(node));
 811
 812         return res;
 813 }
 814
 815 static ir_node *gen_DivMod(ir_node *node)
 816 {
 817         return create_div(node, get_DivMod_left(node), get_DivMod_right(node),
 818                           get_DivMod_resmode(node));
 819 }
 820
 821 static ir_node *gen_Div(ir_node *node)
 822 {
 823         return create_div(node, get_Div_left(node), get_Div_right(node),
 824                           get_Div_resmode(node));
 825 }
 826
 827 static ir_node *gen_Mod(ir_node *node)
 828 {
 829         return create_div(node, get_Mod_left(node), get_Mod_right(node),
 830                           get_Mod_resmode(node));
 831 }
 832
 833 #if 0
 834 static ir_node *gen_node_for_Mul(mips_transform_env_t *env) {
 835         ir_node *node = env->irn;
 836         ir_node *mul;
 837         ir_node *mflo;
 838         ir_node *op1, *op2;
 839         ir_mode *mode = get_irn_mode(node);
 840
 841         op1 = get_Mul_left(node);
 842         op2 = get_Mul_right(node);
 843
 844         assert(get_mode_size_bits(env->mode) == 32);
 845         assert(get_mode_size_bits(get_irn_mode(op1)) == get_mode_size_bits(env->mode));
 846         assert(get_mode_size_bits(get_irn_mode(op2)) == get_mode_size_bits(env->mode));
 847
 848         if(mode_is_signed(mode)) {
 849                 mul = new_rd_mips_mult(env->dbg, env->irg, env->block, get_Mul_left(node), get_Mul_right(node));
 850         } else {
 851                 mul = new_rd_mips_multu(env->dbg, env->irg, env->block, get_Mul_left(node), get_Mul_right(node));
 852         }
 853         mflo = new_rd_mips_mflo(env->dbg, env->irg, env->block, mul);
 854
 855         return mflo;
 856 }
 857
 858 static
 859 ir_node *gen_node_for_IJmp(mips_transform_env_t *env) {
 860         ir_graph *irg    = env->irg;
 861         ir_node  *node   = env->irn;
 862         dbg_info *dbg    = get_irn_dbg_info(node);
 863         ir_node  *block  = get_nodes_block(node);
 864         ir_node  *target = get_IJmp_target(node);
 865
 866         return new_rd_mips_jr(dbg, irg, block, target);
 867 }
 868
 869 static
 870 ir_node *gen_node_for_Rot(mips_transform_env_t *env) {
 871         ir_node *node = env->irn;
 872         ir_node *subu, *srlv, *sllv, *or;
 873
 874         subu = new_rd_mips_subuzero(env->dbg, env->irg, env->block, get_Rot_right(node));
 875         srlv = new_rd_mips_srlv(env->dbg, env->irg, env->block, get_Rot_left(node), subu);
 876         sllv = new_rd_mips_sllv(env->dbg, env->irg, env->block, get_Rot_left(node), get_Rot_right(node));
 877         or = new_rd_mips_or(env->dbg, env->irg, env->block, sllv, srlv);
 878
 879         return or;
 880 }
 881 #endif
 882
 883 static ir_node *gen_Unknown(ir_node *node)
 884 {
 885         (void) node;
 886         assert(mode_needs_gp_reg(get_irn_mode(node)));
 887         return mips_create_zero();
 888 }
 889
 890 #if 0
 891 /*
 892  * lower a copyB into standard Firm assembler :-)
 893  */
 894 ir_node *gen_code_for_CopyB(ir_node *block, ir_node *node) {
 895         ir_node *cnt, *sub;
 896         ir_node *dst = get_CopyB_dst(node);
 897         ir_node *src = get_CopyB_src(node);
 898         ir_type *type = get_CopyB_type(node);
 899         ir_node *mem = get_CopyB_mem(node);
 900         ir_node *mm[4];
 901         ir_node *result = NULL;
 902         int size = get_type_size_bytes(type);
 903         dbg_info *dbg = get_irn_dbg_info(node);
 904         ir_graph *irg = get_irn_irg(block);
 905         mips_attr_t *attr;
 906         int i, n;
 907
 908         if (size > 16) {
 909                 ir_node     *phi, *projT, *projF, *cmp, *proj, *cond, *jmp, *in[2];
 910                 ir_node     *new_bl, *src_phi, *dst_phi, *mem_phi, *add;
 911                 ir_mode     *p_mode = get_irn_mode(src);
 912                 ir_node     *ld[4];
 913
 914                 /* build the control loop */
 915                 in[0] = in[1] = new_r_Unknown(irg, mode_X);
 916
 917                 new_bl = new_r_Block(irg, 2, in);
 918
 919                 in[0] = cnt = new_Const_long(mode_Is, (size >> 4));
 920         in[1] = new_r_Unknown(irg, mode_Is);
 921                 phi   = new_r_Phi(irg, new_bl, 2, in, mode_Is);
 922
 923                 sub = new_rd_Sub(dbg, irg, new_bl, phi, new_Const_long(mode_Is, -1), mode_Is);
 924                 set_Phi_pred(phi, 1, sub);
 925
 926                 cmp = new_rd_Cmp(dbg, irg, new_bl, sub, new_Const_long(mode_Is, 0));
 927                 proj = new_r_Proj(irg, new_bl, cmp, mode_b, pn_Cmp_Lg);
 928                 cond = new_rd_Cond(dbg, irg, new_bl, proj);
 929
 930                 projT = new_r_Proj(irg, new_bl, cond, mode_X, pn_Cond_true);
 931                 projF = new_r_Proj(irg, new_bl, cond, mode_X, pn_Cond_false);
 932
 933                 jmp = get_Block_cfgpred(block, 0);
 934                 set_Block_cfgpred(block, 0, projF);
 935
 936                 set_Block_cfgpred(new_bl, 0, jmp);
 937                 set_Block_cfgpred(new_bl, 1, projT);
 938
 939                 size &= 0xF;
 940
 941                 /* build the copy */
 942                 in[0]   = src;
 943         in[1]   = new_r_Unknown(irg, p_mode);
 944                 src_phi = new_r_Phi(irg, new_bl, 2, in, p_mode);
 945
 946                 in[0]   = dst;
 947                 dst_phi = new_r_Phi(irg, new_bl, 2, in, p_mode);
 948
 949                 add = new_rd_Add(dbg, irg, new_bl, src_phi, new_Const_long(mode_Is, 16), p_mode);
 950                 set_Phi_pred(src_phi, 1, add);
 951                 add = new_rd_Add(dbg, irg, new_bl, dst_phi, new_Const_long(mode_Is, 16), p_mode);
 952                 set_Phi_pred(dst_phi, 1, add);
 953
 954                 in[0]   = mem;
 955         in[1]   = new_r_Unknown(irg, mode_M);
 956                 mem_phi = new_r_Phi(irg, new_bl, 2, in, mode_M);
 957
 958                 src = src_phi;
 959                 dst = dst_phi;
 960
 961                 /* create 4 parallel loads */
 962                 for (i = 0; i < 4; ++i) {
 963                         ir_node *load;
 964
 965                         load = new_rd_mips_load_r(dbg, irg, new_bl, mem_phi, src, mode_T);
 966                         attr = get_mips_attr(load);
 967                         attr->modes.load_store_mode = mode_Iu;
 968                         attr->tv = new_tarval_from_long(i * 4, mode_Iu);
 969
 970                         ld[i] = new_rd_Proj(dbg, irg, new_bl, load, mode_Iu, pn_Load_res);
 971                 }
 972
 973                 /* create 4 parallel stores */
 974                 for (i = 0; i < 4; ++i) {
 975                         ir_node *store;
 976
 977                         store = new_rd_mips_store_r(dbg, irg, new_bl, mem_phi, dst, ld[i], mode_T);
 978                         attr = get_mips_attr(store);
 979                         attr->modes.load_store_mode = mode_Iu;
 980                         attr->tv = new_tarval_from_long(i * 4, mode_Iu);
 981
 982                         mm[i] = new_rd_Proj(dbg, irg, new_bl, store, mode_M, pn_Store_M);
 983                 }
 984                 mem = new_r_Sync(irg, new_bl, 4, mm);
 985                 result = mem;
 986                 set_Phi_pred(mem_phi, 1, mem);
 987         }
 988
 989         // output store/loads manually
 990         n = 0;
 991         for(i = size; i > 0; ) {
 992                 ir_mode *mode;
 993                 ir_node *load, *store, *projv;
 994                 int offset = size - i;
 995                 if(i >= 4) {
 996                         mode = mode_Iu;
 997                         i -= 4;
 998                 } else if(i >= 2) {
 999                         mode = mode_Hu;
1000                         i -= 2;
1001                 } else {
1002                         mode = mode_Bu;
1003                         i -= 1;
1004                 }
1005
1006                 load = new_rd_mips_load_r(dbg, irg, block, mem, src, mode_T);
1007                 attr = get_mips_attr(load);
1008                 attr->modes.load_store_mode = mode;
1009                 attr->tv = new_tarval_from_long(offset, mode_Iu);
1010
1011                 projv = new_rd_Proj(dbg, irg, block, load, mode, pn_Load_res);
1012
1013                 store = new_rd_mips_store_r(dbg, irg, block, mem, dst, projv, mode_T);
1014                 attr = get_mips_attr(store);
1015                 attr->modes.load_store_mode = mode;
1016                 attr->tv = new_tarval_from_long(offset, mode_Iu);
1017
1018                 mm[n] = new_rd_Proj(dbg, irg, block, store, mode_M, pn_Store_M);
1019                 n++;
1020         }
1021
1022         if(n > 0) {
1023                 result = new_r_Sync(irg, block, n, mm);
1024         } else if(n == 1) {
1025                 result = mm[0];
1026         }
1027
1028         return result;
1029 }
1030
1031 static void mips_fix_CopyB_Proj(mips_transform_env_t* env) {
1032         ir_node *node = env->irn;
1033         long n = get_Proj_proj(node);
1034
1035         if(n == pn_CopyB_M_except) {
1036                 panic("Unsupported Proj from CopyB");
1037         } else if(n == pn_CopyB_M_regular) {
1038                 set_Proj_proj(node, pn_Store_M);
1039         } else if(n == pn_CopyB_M_except) {
1040                 set_Proj_proj(node, pn_Store_X_except);
1041         }
1042 }
1043 #endif
1044
1045 static void mips_transform_Spill(mips_transform_env_t* env) {
1046         ir_node   *node = env->irn;
1047         ir_node   *sched_point = NULL;
1048         ir_node   *store;
1049         ir_node   *nomem = new_rd_NoMem(env->irg);
1050         ir_node   *ptr   = get_irn_n(node, 0);
1051         ir_node   *val   = get_irn_n(node, 1);
1052         ir_entity *ent   = be_get_frame_entity(node);
1053
1054         if(sched_is_scheduled(node)) {
1055                 sched_point = sched_prev(node);
1056         }
1057
1058         store = new_rd_mips_sw(env->dbg, env->irg, env->block, ptr, val, nomem,
1059                                ent, 0);
1060
1061         if (sched_point) {
1062                 sched_add_after(sched_point, store);
1063                 sched_remove(node);
1064         }
1065
1066         exchange(node, store);
1067 }
1068
1069 static void mips_transform_Reload(mips_transform_env_t* env) {
1070         ir_node   *node = env->irn;
1071         ir_node   *sched_point = NULL;
1072         ir_node   *load, *proj;
1073         ir_node   *ptr   = get_irn_n(node, 0);
1074         ir_node   *mem   = get_irn_n(node, 1);
1075         ir_entity *ent   = be_get_frame_entity(node);
1076         const arch_register_t* reg;
1077
1078         if(sched_is_scheduled(node)) {
1079                 sched_point = sched_prev(node);
1080         }
1081
1082         load = new_rd_mips_lw(env->dbg, env->irg, env->block, ptr, mem, ent, 0);
1083
1084         proj = new_rd_Proj(env->dbg, env->irg, env->block, load, mode_Iu, pn_mips_lw_res);
1085
1086         if (sched_point) {
1087                 sched_add_after(sched_point, load);
1088
1089                 sched_remove(node);
1090         }
1091
1092         /* copy the register from the old node to the new Load */
1093         reg = arch_get_irn_register(node);
1094         arch_set_irn_register(proj, reg);
1095
1096         exchange(node, proj);
1097 }
1098
1099 #if 0
1100 static ir_node *gen_AddSP(ir_node *node)
1101 {
1102         ir_node *node = env->irn;
1103         ir_node *op1, *op2;
1104         ir_node *add;
1105         const arch_register_t *reg;
1106
1107         op1 = get_irn_n(node, 0);
1108         op2 = get_irn_n(node, 1);
1109
1110         add = new_rd_mips_addu(env->dbg, env->irg, env->block, op1, op2);
1111
1112         /* copy the register requirements from the old node to the new node */
1113         reg = arch_get_irn_register(node);
1114         arch_set_irn_register(add, reg);
1115
1116         return add;
1117 }
1118 #endif
1119
1120 /*********************************************************
1121  *                  _             _      _
1122  *                 (_)           | |    (_)
1123  *  _ __ ___   __ _ _ _ __     __| |_ __ ___   _____ _ __
1124  * | '_ ` _ \ / _` | | '_ \   / _` | '__| \ \ / / _ \ '__|
1125  * | | | | | | (_| | | | | | | (_| | |  | |\ V /  __/ |
1126  * |_| |_| |_|\__,_|_|_| |_|  \__,_|_|  |_| \_/ \___|_|
1127  *
1128  *********************************************************/
1129
1130 typedef ir_node *(*mips_transform_func) (ir_node *node);
1131
1132 static void register_transformer(ir_op *op, mips_transform_func func)
1133 {
1134         assert(op->ops.generic == NULL);
1135         op->ops.generic = (op_func) func;
1136 }
1137
1138 static void register_transformers(void)
1139 {
1140         clear_irp_opcodes_generic_func();
1141
1142         register_transformer(op_Add, gen_Add);
1143         register_transformer(op_Sub, gen_Sub);
1144         register_transformer(op_And, gen_And);
1145         register_transformer(op_Or,  gen_Or);
1146         register_transformer(op_Eor, gen_Eor);
1147         register_transformer(op_Shl, gen_Shl);
1148         register_transformer(op_Shr, gen_Shr);
1149         register_transformer(op_Shrs, gen_Shrs);
1150         register_transformer(op_Not, gen_Not);
1151         register_transformer(op_Minus, gen_Minus);
1152         register_transformer(op_Div, gen_Div);
1153         register_transformer(op_Mod, gen_Mod);
1154         register_transformer(op_DivMod, gen_DivMod);
1155         register_transformer(op_Abs, gen_Abs);
1156         register_transformer(op_Load, gen_Load);
1157         register_transformer(op_Store, gen_Store);
1158         register_transformer(op_Cond, gen_Cond);
1159         register_transformer(op_Conv, gen_Conv);
1160         register_transformer(op_Const, gen_Const);
1161         register_transformer(op_SymConst, gen_SymConst);
1162         register_transformer(op_Unknown, gen_Unknown);
1163         register_transformer(op_Proj, gen_Proj);
1164         register_transformer(op_Phi, gen_Phi);
1165 }
1166
1167 void mips_transform_graph(mips_code_gen_t *cg)
1168 {
1169         register_transformers();
1170         be_transform_graph(cg->birg, NULL);
1171 }
1172
1173 /**
1174  * Calls the transform functions for Spill and Reload.
1175  */
1176 void mips_after_ra_walker(ir_node *node, void *env) {
1177         mips_code_gen_t *cg = env;
1178         mips_transform_env_t tenv;
1179
1180         if (is_Block(node))
1181                 return;
1182
1183         tenv.block = get_nodes_block(node);
1184         tenv.dbg   = get_irn_dbg_info(node);
1185         tenv.irg   = current_ir_graph;
1186         tenv.irn   = node;
1187         tenv.mode  = get_irn_mode(node);
1188         tenv.cg    = cg;
1189
1190         if (be_is_Reload(node)) {
1191                 mips_transform_Reload(&tenv);
1192         } else if (be_is_Spill(node)) {
1193                 mips_transform_Spill(&tenv);
1194         }
1195 }