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