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