js/src/nanojit/LIR.cpp

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 4 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is [Open Source Virtual Machine].
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Adobe System Incorporated.
  19  * Portions created by the Initial Developer are Copyright (C) 2004-2007
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Adobe AS3 Team
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39
  40 #include "nanojit.h"
  41 #include <stdio.h>
  42
  43 namespace nanojit
  44 {
  45     using namespace avmplus;
  46         #ifdef FEATURE_NANOJIT
  47
  48         const uint8_t operandCount[] = {
  49         /* 0 */         2, 2, /*trace*/0, /*nearskip*/0, /*skip*/0, /*neartramp*/0, /*tramp*/0, 2, 2, 2,
  50         /* 10 */        /*param*/0, 2, 2, 2, 2, 2, 2, 2, /*call*/0, /*loop*/0,
  51         /* 20 */        /*x*/0, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  52         /* 30 */        2, 2, /*short*/0, /*int*/0, 2, 2, /*neg*/1, 2, 2, 2,
  53         /* 40 */        /*callh*/1, 2, 2, 2, /*not*/1, 2, 2, 2, /*xt*/1, /*xf*/1,
  54         /* 50 */        /*qlo*/1, /*qhi*/1, 2, /*ov*/1, /*cs*/1, 2, 2, 2, 2, 2,
  55         /* 60 */        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  56         /* 70 */        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  57         /* 80 */        2, 2, /*fcall*/0, 2, 2, 2, 2, 2, 2, 2,
  58         /* 90 */        2, 2, 2, 2, 2, 2, 2, /*quad*/0, 2, 2,
  59         /* 100 */       /*fneg*/1, 2, 2, 2, 2, 2, /*i2f*/1, /*u2f*/1, 2, 2,
  60         /* 110 */       2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  61         /* 120 */       2, 2, 2, 2, 2, 2, 2, 2,
  62         };
  63
  64         // LIR verbose specific
  65         #ifdef NJ_VERBOSE
  66
  67         const char* lirNames[] = {
  68         /* 0-9 */       "0","1","trace","nearskip","skip","neartramp","tramp","7","8","9",
  69         /* 10-19 */     "param","st","ld","13","sti","15","16","17","call","loop",
  70         /* 20-29 */ "x","21","22","23","24","25","feq","flt","fgt","fle",
  71         /* 30-39 */ "fge","cmov","short","int","ldc","","neg","add","sub","mul",
  72         /* 40-49 */ "callh","and","or","xor","not","lsh","rsh","ush","xt","xf",
  73         /* 50-59 */ "qlo","qhi","ldcb","ov","cs","eq","lt","gt","le","ge",
  74         /* 60-63 */ "ult","ugt","ule","uge",
  75         /* 64-69 */ "LIR64","65","66","67","68","69",
  76         /* 70-79 */ "70","71","72","73","74","stq","ldq","77","stqi","79",
  77         /* 80-89 */ "80","81","fcall","83","84","85","86","87","88","89",
  78         /* 90-99 */ "90","91","92","93","94","95","96","quad","98","99",
  79         /* 100-109 */ "fneg","fadd","fsub","fmul","fdiv","qjoin","i2f","u2f","108","109",
  80         /* 110-119 */ "110","111","112","113","114","115","116","117","118","119",
  81         /* 120-127 */ "120","121","122","123","124","125","126","127"
  82         };
  83
  84         #endif /* NANOJIT_VEBROSE */
  85
  86         // implementation
  87
  88 #ifdef NJ_PROFILE
  89         // @todo fixup move to nanojit.h
  90         #undef counter_value
  91         #define counter_value(x)                x
  92 #endif /* NJ_PROFILE */
  93
  94         //static int32_t buffer_count = 0;
  95
  96         // LCompressedBuffer
  97         LirBuffer::LirBuffer(Fragmento* frago, const CallInfo* functions)
  98                 : _frago(frago), _functions(functions)
  99         {
 100                 _start = 0;
 101                 clear();
 102                 _start = pageAlloc();
 103                 if (_start)
 104                 {
 105                         verbose_only(_start->seq = 0;)
 106                         _unused = &_start->lir[0];
 107                 }
 108                 //buffer_count++;
 109                 //fprintf(stderr, "LirBuffer %x start %x\n", (int)this, (int)_start);
 110         }
 111
 112         LirBuffer::~LirBuffer()
 113         {
 114                 //buffer_count--;
 115                 //fprintf(stderr, "~LirBuffer %x start %x\n", (int)this, (int)_start);
 116                 clear();
 117 #ifdef DEBUG
 118         delete names;
 119 #endif
 120                 _frago = 0;
 121         }
 122
 123         void LirBuffer::clear()
 124         {
 125                 // free all the memory and clear the stats
 126                 debug_only( if (_start) validate();)
 127                 while( _start )
 128                 {
 129                         Page *next = _start->next;
 130                         _frago->pageFree( _start );
 131                         _start = next;
 132                         _stats.pages--;
 133                 }
 134                 NanoAssert(_stats.pages == 0);
 135                 _unused = 0;
 136                 _stats.lir = 0;
 137                 _noMem = 0;
 138         }
 139
 140         #ifdef _DEBUG
 141         void LirBuffer::validate() const
 142         {
 143                 uint32_t count = 0;
 144                 Page *last = 0;
 145                 Page *page = _start;
 146                 while(page)
 147                 {
 148                         last = page;
 149                         page = page->next;
 150                         count++;
 151                 }
 152                 NanoAssert(count == _stats.pages);
 153                 NanoAssert(_noMem || _unused->page()->next == 0);
 154                 NanoAssert(_noMem || samepage(last,_unused));
 155         }
 156         #endif
 157
 158 #ifdef NJ_VERBOSE
 159         int LirBuffer::insCount() {
 160                 return _stats.lir;
 161         }
 162         int LirBuffer::byteCount() {
 163                 return (_stats.pages-1) * (sizeof(Page)-sizeof(PageHeader)) +
 164                         (_unused - &_unused->page()->lir[0]) * sizeof(LIns);
 165         }
 166 #endif
 167
 168         Page* LirBuffer::pageAlloc()
 169         {
 170                 Page* page = _frago->pageAlloc();
 171                 if (page)
 172                 {
 173                         page->next = 0; // end of list marker for new page
 174                         _stats.pages++;
 175                 }
 176                 else
 177                 {
 178                         _noMem = 1;
 179                 }
 180                 return page;
 181         }
 182
 183         LInsp LirBuffer::next()
 184         {
 185                 debug_only( validate(); )
 186                 return _unused;
 187         }
 188
 189         bool LirBuffer::addPage()
 190         {
 191                 LInsp last = _unused;
 192                 // we need to pull in a new page and stamp the old one with a link to it
 193         Page *lastPage = last->page();
 194                 Page *page = pageAlloc();
 195                 if (page)
 196                 {
 197                         lastPage->next = page;  // forward link to next page
 198                         _unused = &page->lir[0];
 199             verbose_only(page->seq = lastPage->seq+1;)
 200                         //fprintf(stderr, "Fragmento::ensureRoom stamping %x with %x; start %x unused %x\n", (int)pageBottom(last), (int)page, (int)_start, (int)_unused);
 201                         debug_only( validate(); )
 202                         return true;
 203                 }
 204                 else {
 205                         // mem failure, rewind pointer to top of page so that subsequent instruction works
 206                         verbose_only(if (_frago->assm()->_verbose) _frago->assm()->outputf("page alloc failed");)
 207                         _unused = &lastPage->lir[0];
 208                 }
 209                 return false;
 210         }
 211
 212         bool LirBufWriter::ensureRoom(uint32_t count)
 213         {
 214                 LInsp last = _buf->next();
 215                 if (!samepage(last,last+2*count)
 216                         && _buf->addPage())
 217                 {
 218                         // link LIR stream back to prior instruction (careful insFar relies on _unused...)
 219                         insFar(LIR_skip, last-1);
 220                 }
 221                 return !_buf->outOmem();
 222         }
 223
 224         LInsp LirBuffer::commit(uint32_t count)
 225         {
 226                 debug_only(validate();)
 227                 NanoAssertMsg( samepage(_unused, _unused+count), "You need to call ensureRoom first!" );
 228                 return _unused += count;
 229         }
 230
 231         uint32_t LIns::reference(LIns *r) const
 232         {
 233                 int delta = this-r-1;
 234                 NanoAssert(isU8(delta));
 235                 return delta;
 236         }
 237
 238     LIns* LIns::deref(int32_t off) const
 239     {
 240                 LInsp i = (LInsp) this-1 - off;
 241         while (i->isTramp())
 242             i = i->ref();
 243                 return i;
 244     }
 245
 246         LInsp LirBufWriter::ensureReferenceable(LInsp i, int32_t addedDistance)
 247         {
 248                 NanoAssert(!i->isTramp());
 249                 LInsp next = _buf->next();
 250                 LInsp from = next + 2*addedDistance;
 251                 if (canReference(from,i))
 252                         return i;
 253         if (i == _buf->sp && spref && canReference(from, spref))
 254             return spref;
 255         if (i == _buf->rp && rpref && canReference(from, rpref))
 256             return rpref;
 257
 258                 // need a trampoline to get to i
 259                 LInsp tramp = insFar(LIR_tramp, i);
 260                 NanoAssert( tramp->ref() == i );
 261
 262         if (i == _buf->sp)
 263             spref = tramp;
 264         else if (i == _buf->rp)
 265             rpref = tramp;
 266                 return tramp;
 267         }
 268
 269         LInsp LirBufWriter::insStore(LInsp val, LInsp base, LInsp off)
 270         {
 271                 LOpcode op = val->isQuad() ? LIR_stq : LIR_st;
 272                 NanoAssert(val && base && off);
 273                 ensureRoom(4);
 274                 LInsp r1 = ensureReferenceable(val,3);
 275                 LInsp r2 = ensureReferenceable(base,2);
 276                 LInsp r3 = ensureReferenceable(off,1);
 277
 278                 LInsp l = _buf->next();
 279                 l->initOpcode(op);
 280                 l->setOprnd1(r1);
 281                 l->setOprnd2(r2);
 282                 l->setOprnd3(r3);
 283
 284                 _buf->commit(1);
 285                 _buf->_stats.lir++;
 286                 return l;
 287         }
 288
 289         LInsp LirBufWriter::insStorei(LInsp val, LInsp base, int32_t d)
 290         {
 291                 LOpcode op = val->isQuad() ? LIR_stqi : LIR_sti;
 292                 NanoAssert(val && base && isS8(d));
 293                 ensureRoom(3);
 294                 LInsp r1 = ensureReferenceable(val,2);
 295                 LInsp r2 = ensureReferenceable(base,1);
 296
 297                 LInsp l = _buf->next();
 298                 l->initOpcode(op);
 299                 l->setOprnd1(r1);
 300                 l->setOprnd2(r2);
 301                 l->setDisp(int8_t(d));
 302
 303                 _buf->commit(1);
 304                 _buf->_stats.lir++;
 305                 return l;
 306         }
 307
 308         LInsp LirBufWriter::ins0(LOpcode op)
 309         {
 310                 ensureRoom(1);
 311                 LInsp l = _buf->next();
 312                 l->initOpcode(op);
 313                 _buf->commit(1);
 314                 _buf->_stats.lir++;
 315                 return l;
 316         }
 317
 318         LInsp LirBufWriter::ins1(LOpcode op, LInsp o1)
 319         {
 320                 ensureRoom(2);
 321                 LInsp r1 = ensureReferenceable(o1,1);
 322
 323                 LInsp l = _buf->next();
 324                 l->initOpcode(op);
 325                 if (r1)
 326                         l->setOprnd1(r1);
 327
 328                 _buf->commit(1);
 329                 _buf->_stats.lir++;
 330                 return l;
 331         }
 332
 333         LInsp LirBufWriter::ins2(LOpcode op, LInsp o1, LInsp o2)
 334         {
 335                 ensureRoom(3);
 336                 LInsp r1 = ensureReferenceable(o1,2);
 337                 LInsp r2 = ensureReferenceable(o2,1);
 338
 339                 LInsp l = _buf->next();
 340                 l->initOpcode(op);
 341                 if (r1)
 342                         l->setOprnd1(r1);
 343                 if (r2)
 344                         l->setOprnd2(r2);
 345
 346                 _buf->commit(1);
 347                 _buf->_stats.lir++;
 348                 return l;
 349         }
 350
 351         LInsp LirBufWriter::insLoad(LOpcode op, LInsp base, LInsp d)
 352         {
 353                 return ins2(op,base,d);
 354         }
 355
 356         LInsp LirBufWriter::insGuard(LOpcode op, LInsp c, SideExit *x)
 357         {
 358                 LInsp data = skip(SideExitSize(x));
 359                 *((SideExit*)data->payload()) = *x;
 360                 return ins2(op, c, data);
 361         }
 362
 363     LInsp LirBufWriter::insParam(int32_t arg)
 364     {
 365                 ensureRoom(1);
 366                 LInsp l = _buf->next();
 367                 l->initOpcode(LIR_param);
 368                 l->c.imm8a = Assembler::argRegs[arg];
 369
 370                 _buf->commit(1);
 371                 _buf->_stats.lir++;
 372                 return l;
 373     }
 374
 375 #define isS24(x) (((int32_t(x)<<8)>>8) == (x))
 376
 377         LInsp LirBufWriter::insFar(LOpcode op, LInsp target)
 378         {
 379         NanoAssert(op == LIR_skip || op == LIR_tramp);
 380         LInsp l = _buf->next();
 381         int d = target-l;
 382         if (isS24(d)) {
 383                 ensureRoom(1);
 384             l->initOpcode(LOpcode(op-1)); // nearskip or neartramp
 385             l->t.imm24 = d;
 386             _buf->commit(1);
 387             return l;
 388         }
 389         else {
 390             ensureRoom(2);
 391             // write the pointer and instruction
 392             l = _buf->next()+1;
 393             *((LInsp*)(l-1)) = target;
 394             l->initOpcode(op);
 395             _buf->commit(2);
 396                     return l;
 397         }
 398         }
 399
 400         LInsp LirBufWriter::insImm(int32_t imm)
 401         {
 402                 if (isS16(imm)) {
 403                         ensureRoom(1);
 404                         LInsp l = _buf->next();
 405                         l->initOpcode(LIR_short);
 406                         l->setimm16(imm);
 407                         _buf->commit(1);
 408                         _buf->_stats.lir++;
 409                         return l;
 410                 } else {
 411                         ensureRoom(2);
 412                         int32_t* l = (int32_t*)_buf->next();
 413                         *l = imm;
 414                         _buf->commit(1);
 415                         return ins0(LIR_int);
 416                 }
 417         }
 418
 419         LInsp LirBufWriter::insImmq(uint64_t imm)
 420         {
 421                 ensureRoom(3);
 422                 int32_t* l = (int32_t*)_buf->next();
 423                 l[0] = int32_t(imm);
 424                 l[1] = int32_t(imm>>32);
 425                 _buf->commit(2);
 426                 return ins0(LIR_quad);
 427         }
 428
 429         LInsp LirBufWriter::skip(size_t size)
 430         {
 431         const uint32_t n = (size+sizeof(LIns)-1)/sizeof(LIns);
 432                 ensureRoom(n+2);
 433                 LInsp last = _buf->next()-1;
 434                 _buf->commit(n);
 435                 return insFar(LIR_skip, last);
 436         }
 437
 438         LInsp LirReader::read()
 439         {
 440                 LInsp cur = _i;
 441                 if (!cur)
 442                         return 0;
 443                 LIns* i = cur;
 444                 LOpcode iop = i->opcode();
 445                 do
 446                 {
 447                         switch (iop)
 448                         {
 449                                 default:
 450                                         i--;
 451                                         break;
 452
 453                                 case LIR_call:
 454                                 case LIR_fcall:
 455                                         i -= argwords(i->argc())+1;
 456                                         break;
 457
 458                                 case LIR_skip:
 459                                 case LIR_nearskip:
 460                                         NanoAssert(i->ref() != i);
 461                                         i = i->ref();
 462                                         break;
 463
 464                 case LIR_tramp:
 465                                 case LIR_int:
 466                                         NanoAssert(samepage(i, i-2));
 467                                         i -= 2;
 468                                         break;
 469
 470                                 case LIR_quad:
 471                                         NanoAssert(samepage(i, i-3));
 472                                         i -= 3;
 473                                         break;
 474
 475                                 case LIR_trace:
 476                                         _i = 0;  // start of trace
 477                                         return cur;
 478                         }
 479                         iop = i->opcode();
 480                 }
 481                 while (is_trace_skip_tramp(iop)||iop==LIR_2);
 482                 _i = i;
 483                 return cur;
 484         }
 485
 486         bool FASTCALL isCmp(LOpcode c) {
 487                 return c >= LIR_eq && c <= LIR_uge || c >= LIR_feq && c <= LIR_fge;
 488         }
 489
 490         bool FASTCALL isCond(LOpcode c) {
 491                 return (c == LIR_ov) || (c == LIR_cs) || isCmp(c);
 492         }
 493
 494         bool LIns::isCmp() const {
 495                 return nanojit::isCmp(u.code);
 496         }
 497
 498     bool LIns::isCond() const {
 499         return nanojit::isCond(u.code);
 500     }
 501
 502         bool LIns::isCall() const
 503         {
 504                 return (u.code&~LIR64) == LIR_call;
 505         }
 506
 507         bool LIns::isGuard() const
 508         {
 509                 return u.code==LIR_x || u.code==LIR_xf || u.code==LIR_xt || u.code==LIR_loop;
 510         }
 511
 512     bool LIns::isStore() const
 513     {
 514                 int c = u.code & ~LIR64;
 515         return c == LIR_st || c == LIR_sti;
 516     }
 517
 518     bool LIns::isLoad() const
 519     {
 520         return u.code == LIR_ldq || u.code == LIR_ld || u.code == LIR_ldc;
 521     }
 522
 523         bool LIns::isconst() const
 524         {
 525                 return (opcode()&~1) == LIR_short;
 526         }
 527
 528         bool LIns::isconstval(int32_t val) const
 529         {
 530                 return isconst() && constval()==val;
 531         }
 532
 533         bool LIns::isconstq() const
 534         {
 535                 return isop(LIR_quad);
 536         }
 537
 538         bool LIns::isconstp() const
 539         {
 540     #ifdef AVMPLUS_64BIT
 541             return isconstq();
 542         #else
 543             return isconst();
 544     #endif
 545         }
 546
 547         bool FASTCALL isCse(LOpcode op) {
 548                 op = LOpcode(op & ~LIR64);
 549                 return op >= LIR_feq && op <= LIR_uge;
 550         }
 551
 552     bool LIns::isCse(const CallInfo *functions) const
 553     {
 554                 return nanojit::isCse(u.code) || isCall() && functions[fid()]._cse;
 555     }
 556
 557         void LIns::setimm16(int32_t x)
 558         {
 559                 NanoAssert(isS16(x));
 560                 i.imm16 = int16_t(x);
 561         }
 562
 563         void LIns::setresv(uint32_t resv)
 564         {
 565                 NanoAssert(isU8(resv));
 566                 g.resv = resv;
 567         }
 568
 569         void LIns::initOpcode(LOpcode op)
 570         {
 571                 i.code = op;
 572                 i.imm16 = 0;
 573         i.resv = 0;
 574         }
 575
 576         void LIns::setOprnd1(LInsp r)
 577         {
 578                 u.oprnd_1 = reference(r);
 579         }
 580
 581         void LIns::setOprnd2(LInsp r)
 582         {
 583                 u.oprnd_2 = reference(r);
 584         }
 585
 586         void LIns::setOprnd3(LInsp r)
 587         {
 588                 u.oprnd_3 = reference(r);
 589         }
 590
 591     void LIns::setDisp(int8_t d)
 592     {
 593         sti.disp = d;
 594     }
 595
 596         LInsp   LIns::oprnd1() const
 597         {
 598         return deref(u.oprnd_1);
 599         }
 600
 601         LInsp   LIns::oprnd2() const
 602         {
 603         return deref(u.oprnd_2);
 604         }
 605
 606         LInsp   LIns::oprnd3() const
 607         {
 608         return deref(u.oprnd_3);
 609         }
 610
 611     void *LIns::payload() const
 612     {
 613         NanoAssert(opcode()==LIR_skip || opcode()==LIR_nearskip);
 614         return (void*) (ref()+1);
 615     }
 616
 617     LIns* LirWriter::ins2i(LOpcode v, LIns* oprnd1, int32_t imm)
 618     {
 619         return ins2(v, oprnd1, insImm(imm));
 620     }
 621
 622     bool insIsS16(LInsp i)
 623     {
 624         if (i->isconst()) {
 625             int c = i->constval();
 626             return isS16(c);
 627         }
 628         if (i->isop(LIR_cmov)) {
 629             LInsp vals = i->oprnd2();
 630             return insIsS16(vals->oprnd1()) && insIsS16(vals->oprnd2());
 631         }
 632         if (i->isCmp())
 633             return true;
 634         // many other possibilities too.
 635         return false;
 636     }
 637
 638         LIns* ExprFilter::ins1(LOpcode v, LIns* i)
 639         {
 640                 if (v == LIR_qlo) {
 641                         if (i->isconstq())
 642                                 return insImm(int32_t(i->constvalq()));
 643                         if (i->isop(LIR_qjoin))
 644                                 return i->oprnd1();
 645                 }
 646                 else if (v == LIR_qhi) {
 647                         if (i->isconstq())
 648                                 return insImm(int32_t(i->constvalq()>>32));
 649                         if (i->isop(LIR_qjoin))
 650                                 return i->oprnd2();
 651                 }
 652                 else if (v == i->opcode() && (v == LIR_not || v == LIR_neg || v == LIR_fneg)) {
 653                         return i->oprnd1();
 654                 }
 655
 656                 // todo
 657                 // -(a-b) = b-a
 658
 659                 return out->ins1(v, i);
 660         }
 661
 662         LIns* ExprFilter::ins2(LOpcode v, LIns* oprnd1, LIns* oprnd2)
 663         {
 664                 NanoAssert(oprnd1 && oprnd2);
 665                 if (v == LIR_cmov) {
 666                         if (oprnd2->oprnd1() == oprnd2->oprnd2()) {
 667                                 // c ? a : a => a
 668                                 return oprnd2->oprnd1();
 669                         }
 670                 }
 671                 if (oprnd1 == oprnd2)
 672                 {
 673                         if (v == LIR_xor || v == LIR_sub ||
 674                                 v == LIR_ult || v == LIR_ugt || v == LIR_gt || v == LIR_lt)
 675                                 return insImm(0);
 676                         if (v == LIR_or || v == LIR_and)
 677                                 return oprnd1;
 678                         if (v == LIR_le || v == LIR_ule || v == LIR_ge || v == LIR_uge) {
 679                                 // x <= x == 1; x >= x == 1
 680                                 return insImm(1);
 681                         }
 682                 }
 683                 if (oprnd1->isconst() && oprnd2->isconst())
 684                 {
 685                         int c1 = oprnd1->constval();
 686                         int c2 = oprnd2->constval();
 687                         if (v == LIR_qjoin) {
 688                                 uint64_t q = c1 | uint64_t(c2)<<32;
 689                                 return insImmq(q);
 690                         }
 691                         if (v == LIR_eq)
 692                                 return insImm(c1 == c2);
 693             if (v == LIR_ov)
 694                 return insImm((c2 != 0) && ((c1 + c2) <= c1));
 695             if (v == LIR_cs)
 696                 return insImm((c2 != 0) && ((uint32_t(c1) + uint32_t(c2)) <= uint32_t(c1)));
 697                         if (v == LIR_lt)
 698                                 return insImm(c1 < c2);
 699                         if (v == LIR_gt)
 700                                 return insImm(c1 > c2);
 701                         if (v == LIR_le)
 702                                 return insImm(c1 <= c2);
 703                         if (v == LIR_ge)
 704                                 return insImm(c1 >= c2);
 705                         if (v == LIR_ult)
 706                                 return insImm(uint32_t(c1) < uint32_t(c2));
 707                         if (v == LIR_ugt)
 708                                 return insImm(uint32_t(c1) > uint32_t(c2));
 709                         if (v == LIR_ule)
 710                                 return insImm(uint32_t(c1) <= uint32_t(c2));
 711                         if (v == LIR_uge)
 712                                 return insImm(uint32_t(c1) >= uint32_t(c2));
 713                         if (v == LIR_rsh)
 714                                 return insImm(int32_t(c1) >> int32_t(c2));
 715                         if (v == LIR_lsh)
 716                                 return insImm(int32_t(c1) << int32_t(c2));
 717                         if (v == LIR_ush)
 718                                 return insImm(uint32_t(c1) >> int32_t(c2));
 719                 }
 720                 else if (oprnd1->isconstq() && oprnd2->isconstq())
 721                 {
 722                         double c1 = oprnd1->constvalf();
 723                         double c2 = oprnd1->constvalf();
 724                         if (v == LIR_feq)
 725                                 return insImm(c1 == c2);
 726                         if (v == LIR_flt)
 727                                 return insImm(c1 < c2);
 728                         if (v == LIR_fgt)
 729                                 return insImm(c1 > c2);
 730                         if (v == LIR_fle)
 731                                 return insImm(c1 <= c2);
 732                         if (v == LIR_fge)
 733                                 return insImm(c1 >= c2);
 734                 }
 735                 else if (oprnd1->isconst() && !oprnd2->isconst())
 736                 {
 737                         if (v == LIR_add || v == LIR_mul ||
 738                                 v == LIR_fadd || v == LIR_fmul ||
 739                                 v == LIR_xor || v == LIR_or || v == LIR_and ||
 740                                 v == LIR_eq) {
 741                                 // move const to rhs
 742                                 LIns* t = oprnd2;
 743                                 oprnd2 = oprnd1;
 744                                 oprnd1 = t;
 745                         }
 746                         else if (v >= LIR_lt && v <= LIR_uge) {
 747                                 // move const to rhs, swap the operator
 748                                 LIns *t = oprnd2;
 749                                 oprnd2 = oprnd1;
 750                                 oprnd1 = t;
 751                                 v = LOpcode(v^1);
 752                         }
 753                         else if (v == LIR_cmov) {
 754                                 // const ? x : y => return x or y depending on const
 755                                 return oprnd1->constval() ? oprnd2->oprnd1() : oprnd2->oprnd2();
 756                         }
 757                 }
 758
 759                 if (oprnd2->isconst())
 760                 {
 761                         int c = oprnd2->constval();
 762                         if (v == LIR_add && oprnd1->isop(LIR_add) && oprnd1->oprnd2()->isconst()) {
 763                                 // add(add(x,c1),c2) => add(x,c1+c2)
 764                                 c += oprnd1->oprnd2()->constval();
 765                                 oprnd2 = insImm(c);
 766                                 oprnd1 = oprnd1->oprnd1();
 767                         }
 768                         else if (v == LIR_sub && oprnd1->isop(LIR_add) && oprnd1->oprnd2()->isconst()) {
 769                                 // sub(add(x,c1),c2) => add(x,c1-c2)
 770                                 c = oprnd1->oprnd2()->constval() - c;
 771                                 oprnd2 = insImm(c);
 772                                 oprnd1 = oprnd1->oprnd1();
 773                                 v = LIR_add;
 774                         }
 775                         else if (v == LIR_rsh && c == 16 && oprnd1->isop(LIR_lsh) &&
 776                                          oprnd1->oprnd2()->isconstval(16)) {
 777                                 if (insIsS16(oprnd1->oprnd1())) {
 778                                         // rsh(lhs(x,16),16) == x, if x is S16
 779                                         return oprnd1->oprnd1();
 780                                 }
 781                         }
 782                         else if (v == LIR_ult) {
 783                                 if (oprnd1->isop(LIR_cmov)) {
 784                                         LInsp a = oprnd1->oprnd2()->oprnd1();
 785                                         LInsp b = oprnd1->oprnd2()->oprnd2();
 786                                         if (a->isconst() && b->isconst()) {
 787                                                 bool a_lt = uint32_t(a->constval()) < uint32_t(oprnd2->constval());
 788                                                 bool b_lt = uint32_t(b->constval()) < uint32_t(oprnd2->constval());
 789                                                 if (a_lt == b_lt)
 790                                                         return insImm(a_lt);
 791                                         }
 792                                 }
 793                         }
 794
 795                         if (c == 0)
 796                         {
 797                                 if (v == LIR_add || v == LIR_or || v == LIR_xor ||
 798                                         v == LIR_sub || v == LIR_lsh || v == LIR_rsh || v == LIR_ush)
 799                                         return oprnd1;
 800                                 else if (v == LIR_and || v == LIR_mul)
 801                                         return oprnd2;
 802                                 else if (v == LIR_eq && oprnd1->isop(LIR_or) &&
 803                                         oprnd1->oprnd2()->isconst() &&
 804                                         oprnd1->oprnd2()->constval() != 0) {
 805                                         // (x or c) != 0 if c != 0
 806                                         return insImm(0);
 807                                 }
 808                         }
 809                         else if (c == -1 || c == 1 && oprnd1->isCmp()) {
 810                                 if (v == LIR_or) {
 811                                         // x | -1 = -1, cmp | 1 = 1
 812                                         return oprnd2;
 813                                 }
 814                                 else if (v == LIR_and) {
 815                                         // x & -1 = x, cmp & 1 = cmp
 816                                         return oprnd1;
 817                                 }
 818                         }
 819                 }
 820
 821                 LInsp i;
 822                 if (v == LIR_qjoin && oprnd1->isop(LIR_qlo) && oprnd2->isop(LIR_qhi)
 823                         && (i = oprnd1->oprnd1()) == oprnd1->oprnd1()) {
 824                         // qjoin(qlo(x),qhi(x)) == x
 825                         return i;
 826                 }
 827
 828                 return out->ins2(v, oprnd1, oprnd2);
 829         }
 830
 831         LIns* ExprFilter::insGuard(LOpcode v, LInsp c, SideExit *x)
 832         {
 833                 if (v == LIR_xt || v == LIR_xf) {
 834                         if (c->isconst()) {
 835                                 if (v == LIR_xt && !c->constval() || v == LIR_xf && c->constval()) {
 836                                         return 0; // no guard needed
 837                                 }
 838                                 else {
 839                                         // need a way to EOT now, since this is trace end.
 840                                         return out->insGuard(LIR_x, out->insImm(1), x);
 841                                 }
 842                         }
 843                         else {
 844                                 while (c->isop(LIR_eq) && c->oprnd1()->isCmp() &&
 845                                         c->oprnd2()->isconstval(0)) {
 846                                     // xt(eq(cmp,0)) => xf(cmp)   or   xf(eq(cmp,0)) => xt(cmp)
 847                                     v = LOpcode(v^1);
 848                                     c = c->oprnd1();
 849                                 }
 850                         }
 851                 }
 852                 return out->insGuard(v, c, x);
 853         }
 854
 855     LIns* LirWriter::insLoadi(LIns *base, int disp)
 856     {
 857         return insLoad(LIR_ld,base,disp);
 858     }
 859
 860         LIns* LirWriter::insLoad(LOpcode op, LIns *base, int disp)
 861         {
 862                 return insLoad(op, base, insImm(disp));
 863         }
 864
 865         LIns* LirWriter::ins_eq0(LIns* oprnd1)
 866         {
 867                 return ins2i(LIR_eq, oprnd1, 0);
 868         }
 869
 870         LIns* LirWriter::qjoin(LInsp lo, LInsp hi)
 871         {
 872                 return ins2(LIR_qjoin, lo, hi);
 873         }
 874
 875         LIns* LirWriter::insImmPtr(const void *ptr)
 876         {
 877                 return sizeof(ptr) == 8 ? insImmq((uintptr_t)ptr) : insImm((intptr_t)ptr);
 878         }
 879
 880         LIns* LirWriter::ins_choose(LIns* cond, LIns* iftrue, LIns* iffalse, bool hasConditionalMove)
 881         {
 882                 // if not a conditional, make it implicitly an ==0 test (then flop results)
 883                 if (!cond->isCmp())
 884                 {
 885                         cond = ins_eq0(cond);
 886                         LInsp tmp = iftrue;
 887                         iftrue = iffalse;
 888                         iffalse = tmp;
 889                 }
 890
 891                 if (hasConditionalMove)
 892                 {
 893                         return ins2(LIR_cmov, cond, ins2(LIR_2, iftrue, iffalse));
 894                 }
 895
 896                 // @todo -- it might be better to use a short conditional branch rather than
 897                 // the bit-twiddling on systems that don't provide a conditional move instruction.
 898                 LInsp ncond = ins1(LIR_neg, cond); // cond ? -1 : 0
 899                 return ins2(LIR_or,
 900                                         ins2(LIR_and, iftrue, ncond),
 901                                         ins2(LIR_and, iffalse, ins1(LIR_not, ncond)));
 902         }
 903
 904     LIns* LirBufWriter::insCall(uint32_t fid, LInsp args[])
 905         {
 906                 static const LOpcode k_callmap[] = { LIR_call, LIR_fcall, LIR_call, LIR_callh };
 907
 908                 const CallInfo& ci = _functions[fid];
 909                 uint32_t argt = ci._argtypes;
 910                 LOpcode op = k_callmap[argt & 3];
 911
 912         ArgSize sizes[10];
 913         uint32_t argc = ci.get_sizes(sizes);
 914
 915 #ifdef NJ_SOFTFLOAT
 916                 if (op == LIR_fcall)
 917                         op = LIR_callh;
 918                 LInsp args2[5*2]; // arm could require 2 args per double
 919                 int32_t j = 0;
 920                 for (int32_t i = 0; i < 5; i++) {
 921                         argt >>= 2;
 922                         ArgSize a = ArgSize(argt&3);
 923                         if (a == ARGSIZE_F) {
 924                                 LInsp q = args[i];
 925                                 args2[j++] = ins1(LIR_qhi, q);
 926                                 args2[j++] = ins1(LIR_qlo, q);
 927                         } else if (a != ARGSIZE_NONE) {
 928                                 args2[j++] = args[i];
 929                         }
 930                 }
 931                 args = args2;
 932         NanoAssert(j == argc);
 933 #endif
 934
 935                 NanoAssert(argc < 8);
 936                 uint32_t words = argwords(argc);
 937                 ensureRoom(words+argc+1);  // ins size + possible tramps
 938                 for (uint32_t i=0; i < argc; i++)
 939                         args[i] = ensureReferenceable(args[i], argc-i);
 940                 uint8_t* offs = (uint8_t*)_buf->next();
 941                 LIns *l = _buf->next() + words;
 942                 for (uint32_t i=0; i < argc; i++)
 943                         offs[i] = (uint8_t) l->reference(args[i]);
 944                 l->initOpcode(op==LIR_callh ? LIR_call : op);
 945         l->c.imm8a = fid;
 946         l->c.imm8b = argc;
 947                 _buf->commit(words+1);
 948                 _buf->_stats.lir++;
 949                 return l;
 950         }
 951
 952     using namespace avmplus;
 953
 954         StackFilter::StackFilter(LirFilter *in, GC *gc, Fragment *frag, LInsp sp)
 955                 : LirFilter(in), gc(gc), frag(frag), sp(sp), top(0)
 956         {}
 957
 958         LInsp StackFilter::read()
 959         {
 960                 for (;;)
 961                 {
 962                         LInsp i = in->read();
 963                         if (!i)
 964                                 return i;
 965                         if (i->isStore())
 966                         {
 967                                 LInsp base = i->oprnd2();
 968                                 if (base == sp)
 969                                 {
 970                                         LInsp v = i->oprnd1();
 971                                         int d = i->immdisp() >> 2;
 972                                         if (d >= top) {
 973                                                 continue;
 974                                         } else {
 975                                                 d = top - d;
 976                                                 if (v->isQuad()) {
 977                                                         // storing 8 bytes
 978                                                         if (stk.get(d) && stk.get(d-1)) {
 979                                                                 continue;
 980                                                         } else {
 981                                                                 stk.set(gc, d);
 982                                                                 stk.set(gc, d-1);
 983                                                         }
 984                                                 }
 985                                                 else {
 986                                                         // storing 4 bytes
 987                                                         if (stk.get(d))
 988                                                                 continue;
 989                                                         else
 990                                                                 stk.set(gc, d);
 991                                                 }
 992                                         }
 993                                 }
 994                         }
 995                         else if (i->isGuard())
 996                         {
 997                                 stk.reset();
 998                                 top = getTop(i) >> 2;
 999                         }
1000                         return i;
1001                 }
1002         }
1003
1004         //
1005         // inlined/separated version of SuperFastHash
1006         // This content is copyrighted by Paul Hsieh, For reference see : http://www.azillionmonkeys.com/qed/hash.html
1007         //
1008         inline uint32_t _hash8(uint32_t hash, const uint8_t data)
1009         {
1010                 hash += data;
1011                 hash ^= hash << 10;
1012                 hash += hash >> 1;
1013                 return hash;
1014         }
1015
1016         inline uint32_t _hash32(uint32_t hash, const uint32_t data)
1017         {
1018                 const uint32_t dlo = data & 0xffff;
1019                 const uint32_t dhi = data >> 16;
1020                 hash += dlo;
1021                 const uint32_t tmp = (dhi << 11) ^ hash;
1022                 hash = (hash << 16) ^ tmp;
1023                 hash += hash >> 11;
1024                 return hash;
1025         }
1026
1027         inline uint32_t _hashptr(uint32_t hash, const void* data)
1028         {
1029 #ifdef NANOJIT_64BIT
1030                 hash = _hash32(hash, uint32_t(uintptr_t(data) >> 32));
1031                 hash = _hash32(hash, uint32_t(uintptr_t(data)));
1032                 return hash;
1033 #else
1034                 return _hash32(hash, uint32_t(data));
1035 #endif
1036         }
1037
1038         inline uint32_t _hashfinish(uint32_t hash)
1039         {
1040                 /* Force "avalanching" of final 127 bits */
1041                 hash ^= hash << 3;
1042                 hash += hash >> 5;
1043                 hash ^= hash << 4;
1044                 hash += hash >> 17;
1045                 hash ^= hash << 25;
1046                 hash += hash >> 6;
1047                 return hash;
1048         }
1049
1050         LInsHashSet::LInsHashSet(GC* gc) :
1051                         m_list(gc, kInitialCap), m_used(0), m_gc(gc)
1052         {
1053 #ifdef MEMORY_INFO
1054                 m_list.set_meminfo_name("LInsHashSet.list");
1055 #endif
1056                 m_list.set(kInitialCap-1, 0);
1057         }
1058
1059         /*static*/ uint32_t FASTCALL LInsHashSet::hashcode(LInsp i)
1060         {
1061                 const LOpcode op = i->opcode();
1062                 switch (op)
1063                 {
1064                         case LIR_short:
1065                                 return hashimm(i->imm16());
1066                         case LIR_int:
1067                                 return hashimm(i->imm32());
1068                         case LIR_quad:
1069                                 return hashimmq(i->constvalq());
1070                         case LIR_call:
1071                         case LIR_fcall:
1072                         {
1073                                 LInsp args[10];
1074                                 int32_t argc = i->argc();
1075                                 NanoAssert(argc < 10);
1076                                 for (int32_t j=0; j < argc; j++)
1077                                         args[j] = i->arg(j);
1078                                 return hashcall(i->fid(), argc, args);
1079                         }
1080                         default:
1081                                 if (operandCount[op] == 2)
1082                                         return hash2(op, i->oprnd1(), i->oprnd2());
1083                                 else
1084                                         return hash1(op, i->oprnd1());
1085                 }
1086         }
1087
1088         /*static*/ bool FASTCALL LInsHashSet::equals(LInsp a, LInsp b)
1089         {
1090                 if (a==b)
1091                         return true;
1092                 AvmAssert(a->opcode() == b->opcode());
1093                 const LOpcode op = a->opcode();
1094                 switch (op)
1095                 {
1096                         case LIR_short:
1097                         {
1098                                 return a->imm16() == b->imm16();
1099                         }
1100                         case LIR_int:
1101                         {
1102                                 return a->imm32() == b->imm32();
1103                         }
1104                         case LIR_quad:
1105                         {
1106                                 return a->constvalq() == b->constvalq();
1107                         }
1108                         case LIR_call:
1109                         case LIR_fcall:
1110                         {
1111                                 if (a->fid() != b->fid()) return false;
1112                                 uint32_t argc=a->argc();
1113                 NanoAssert(argc == b->argc());
1114                                 for (uint32_t i=0; i < argc; i++)
1115                                         if (a->arg(i) != b->arg(i))
1116                                                 return false;
1117                                 return true;
1118                         }
1119                         default:
1120                         {
1121                                 const uint32_t count = operandCount[op];
1122                                 if ((count >= 1 && a->oprnd1() != b->oprnd1()) ||
1123                                         (count >= 2 && a->oprnd2() != b->oprnd2()))
1124                                         return false;
1125                                 return true;
1126                         }
1127                 }
1128         }
1129
1130         void FASTCALL LInsHashSet::grow()
1131         {
1132                 const uint32_t newcap = m_list.size() << 1;
1133                 InsList newlist(m_gc, newcap);
1134 #ifdef MEMORY_INFO
1135                 newlist.set_meminfo_name("LInsHashSet.list");
1136 #endif
1137                 newlist.set(newcap-1, 0);
1138                 for (uint32_t i=0, n=m_list.size(); i < n; i++)
1139                 {
1140                         LInsp name = m_list.get(i);
1141                         if (!name) continue;
1142                         uint32_t j = find(name, hashcode(name), newlist, newcap);
1143                         newlist.set(j, name);
1144                 }
1145                 m_list.become(newlist);
1146         }
1147
1148         uint32_t FASTCALL LInsHashSet::find(LInsp name, uint32_t hash, const InsList& list, uint32_t cap)
1149         {
1150                 const uint32_t bitmask = (cap - 1) & ~0x1;
1151
1152                 uint32_t n = 7 << 1;
1153                 hash &= bitmask;
1154                 LInsp k;
1155                 while ((k = list.get(hash)) != NULL &&
1156                         (!LIns::sameop(k,name) || !equals(k, name)))
1157                 {
1158                         hash = (hash + (n += 2)) & bitmask;             // quadratic probe
1159                 }
1160                 return hash;
1161         }
1162
1163         LInsp LInsHashSet::add(LInsp name, uint32_t k)
1164         {
1165                 // this is relatively short-lived so let's try a more aggressive load factor
1166                 // in the interest of improving performance
1167                 if (((m_used+1)<<1) >= m_list.size()) // 0.50
1168                 {
1169                         grow();
1170                         k = find(name, hashcode(name), m_list, m_list.size());
1171                 }
1172                 NanoAssert(!m_list.get(k));
1173                 m_used++;
1174                 m_list.set(k, name);
1175                 return name;
1176         }
1177
1178         void LInsHashSet::replace(LInsp i)
1179         {
1180                 uint32_t k = find(i, hashcode(i), m_list, m_list.size());
1181                 if (m_list.get(k)) {
1182                         // already there, so replace it
1183                         m_list.set(k, i);
1184                 } else {
1185                         add(i, k);
1186                 }
1187         }
1188
1189         uint32_t LInsHashSet::hashimm(int32_t a) {
1190                 return _hashfinish(_hash32(0,a));
1191         }
1192
1193         uint32_t LInsHashSet::hashimmq(uint64_t a) {
1194                 uint32_t hash = _hash32(0, uint32_t(a >> 32));
1195                 return _hashfinish(_hash32(hash, uint32_t(a)));
1196         }
1197
1198         uint32_t LInsHashSet::hash1(LOpcode op, LInsp a) {
1199                 uint32_t hash = _hash8(0,uint8_t(op));
1200                 return _hashfinish(_hashptr(hash, a));
1201         }
1202
1203         uint32_t LInsHashSet::hash2(LOpcode op, LInsp a, LInsp b) {
1204                 uint32_t hash = _hash8(0,uint8_t(op));
1205                 hash = _hashptr(hash, a);
1206                 return _hashfinish(_hashptr(hash, b));
1207         }
1208
1209         uint32_t LInsHashSet::hashcall(uint32_t fid, uint32_t argc, LInsp args[]) {
1210                 uint32_t hash = _hash32(0,fid);
1211                 for (int32_t j=argc-1; j >= 0; j--)
1212                         hash = _hashptr(hash,args[j]);
1213                 return _hashfinish(hash);
1214         }
1215
1216         LInsp LInsHashSet::find32(int32_t a, uint32_t &i)
1217         {
1218                 uint32_t cap = m_list.size();
1219                 const InsList& list = m_list;
1220                 const uint32_t bitmask = (cap - 1) & ~0x1;
1221                 uint32_t hash = hashimm(a) & bitmask;
1222                 uint32_t n = 7 << 1;
1223                 LInsp k;
1224                 while ((k = list.get(hash)) != NULL &&
1225                         (!k->isconst() || k->constval() != a))
1226                 {
1227                         hash = (hash + (n += 2)) & bitmask;             // quadratic probe
1228                 }
1229                 i = hash;
1230                 return k;
1231         }
1232
1233         LInsp LInsHashSet::find64(uint64_t a, uint32_t &i)
1234         {
1235                 uint32_t cap = m_list.size();
1236                 const InsList& list = m_list;
1237                 const uint32_t bitmask = (cap - 1) & ~0x1;
1238                 uint32_t hash = hashimmq(a) & bitmask;
1239                 uint32_t n = 7 << 1;
1240                 LInsp k;
1241                 while ((k = list.get(hash)) != NULL &&
1242                         (!k->isconstq() || k->constvalq() != a))
1243                 {
1244                         hash = (hash + (n += 2)) & bitmask;             // quadratic probe
1245                 }
1246                 i = hash;
1247                 return k;
1248         }
1249
1250         LInsp LInsHashSet::find1(LOpcode op, LInsp a, uint32_t &i)
1251         {
1252                 uint32_t cap = m_list.size();
1253                 const InsList& list = m_list;
1254                 const uint32_t bitmask = (cap - 1) & ~0x1;
1255                 uint32_t hash = hash1(op,a) & bitmask;
1256                 uint32_t n = 7 << 1;
1257                 LInsp k;
1258                 while ((k = list.get(hash)) != NULL &&
1259                         (k->opcode() != op || k->oprnd1() != a))
1260                 {
1261                         hash = (hash + (n += 2)) & bitmask;             // quadratic probe
1262                 }
1263                 i = hash;
1264                 return k;
1265         }
1266
1267         LInsp LInsHashSet::find2(LOpcode op, LInsp a, LInsp b, uint32_t &i)
1268         {
1269                 uint32_t cap = m_list.size();
1270                 const InsList& list = m_list;
1271                 const uint32_t bitmask = (cap - 1) & ~0x1;
1272                 uint32_t hash = hash2(op,a,b) & bitmask;
1273                 uint32_t n = 7 << 1;
1274                 LInsp k;
1275                 while ((k = list.get(hash)) != NULL &&
1276                         (k->opcode() != op || k->oprnd1() != a || k->oprnd2() != b))
1277                 {
1278                         hash = (hash + (n += 2)) & bitmask;             // quadratic probe
1279                 }
1280                 i = hash;
1281                 return k;
1282         }
1283
1284         bool argsmatch(LInsp i, uint32_t argc, LInsp args[])
1285         {
1286                 for (uint32_t j=0; j < argc; j++)
1287                         if (i->arg(j) != args[j])
1288                                 return false;
1289                 return true;
1290         }
1291
1292         LInsp LInsHashSet::findcall(uint32_t fid, uint32_t argc, LInsp args[], uint32_t &i)
1293         {
1294                 uint32_t cap = m_list.size();
1295                 const InsList& list = m_list;
1296                 const uint32_t bitmask = (cap - 1) & ~0x1;
1297                 uint32_t hash = hashcall(fid, argc, args) & bitmask;
1298                 uint32_t n = 7 << 1;
1299                 LInsp k;
1300                 while ((k = list.get(hash)) != NULL &&
1301                         (!k->isCall() || k->fid() != fid || !argsmatch(k, argc, args)))
1302                 {
1303                         hash = (hash + (n += 2)) & bitmask;             // quadratic probe
1304                 }
1305                 i = hash;
1306                 return k;
1307         }
1308
1309     SideExit *LIns::exit()
1310     {
1311         NanoAssert(isGuard());
1312         return (SideExit*)oprnd2()->payload();
1313     }
1314
1315 #ifdef NJ_VERBOSE
1316     class RetiredEntry: public GCObject
1317     {
1318     public:
1319         List<LInsp, LIST_NonGCObjects> live;
1320         LInsp i;
1321         RetiredEntry(GC *gc): live(gc) {}
1322     };
1323         class LiveTable
1324         {
1325         public:
1326                 SortedMap<LInsp,LInsp,LIST_NonGCObjects> live;
1327         List<RetiredEntry*, LIST_GCObjects> retired;
1328                 int maxlive;
1329                 LiveTable(GC *gc) : live(gc), retired(gc), maxlive(0) {}
1330         ~LiveTable()
1331         {
1332             for (size_t i = 0; i < retired.size(); i++) {
1333                 delete retired.get(i);
1334             }
1335
1336         }
1337                 void add(LInsp i, LInsp use) {
1338             if (!i->isconst() && !i->isconstq() && !live.containsKey(i)) {
1339                 live.put(i,use);
1340             }
1341                 }
1342         void retire(LInsp i, GC *gc) {
1343             RetiredEntry *e = new (gc) RetiredEntry(gc);
1344             e->i = i;
1345             for (int j=0, n=live.size(); j < n; j++) {
1346                 LInsp l = live.keyAt(j);
1347                 if (!l->isStore() && !l->isGuard())
1348                     e->live.add(l);
1349             }
1350             int size=0;
1351                     if ((size = e->live.size()) > maxlive)
1352                             maxlive = size;
1353
1354             live.remove(i);
1355             retired.add(e);
1356                 }
1357                 bool contains(LInsp i) {
1358                         return live.containsKey(i);
1359                 }
1360         };
1361
1362     void live(GC *gc, Assembler *assm, Fragment *frag)
1363         {
1364                 // traverse backwards to find live exprs and a few other stats.
1365
1366                 LInsp sp = frag->lirbuf->sp;
1367                 LInsp rp = frag->lirbuf->rp;
1368                 LiveTable live(gc);
1369                 uint32_t exits = 0;
1370                 LirBuffer *lirbuf = frag->lirbuf;
1371         LirReader br(lirbuf);
1372                 StackFilter sf(&br, gc, frag, sp);
1373                 StackFilter r(&sf, gc, frag, rp);
1374         int total = 0;
1375         live.add(frag->lirbuf->state, r.pos());
1376                 for (LInsp i = r.read(); i != 0; i = r.read())
1377                 {
1378             total++;
1379
1380             // first handle side-effect instructions
1381                         if (i->isStore() || i->isGuard() ||
1382                                 i->isCall() && !assm->callInfoFor(i->fid())->_cse)
1383                         {
1384                                 live.add(i,0);
1385                 if (i->isGuard())
1386                     exits++;
1387                         }
1388
1389                         // now propagate liveness
1390                         if (live.contains(i))
1391                         {
1392                                 live.retire(i,gc);
1393                                 if (i->isStore()) {
1394                                         live.add(i->oprnd2(),i); // base
1395                                         live.add(i->oprnd1(),i); // val
1396                                 }
1397                 else if (i->isop(LIR_cmov)) {
1398                     live.add(i->oprnd1(),i);
1399                     live.add(i->oprnd2()->oprnd1(),i);
1400                     live.add(i->oprnd2()->oprnd2(),i);
1401                 }
1402                                 else if (operandCount[i->opcode()] == 1) {
1403                                     live.add(i->oprnd1(),i);
1404                                 }
1405                                 else if (operandCount[i->opcode()] == 2) {
1406                                         live.add(i->oprnd1(),i);
1407                                         live.add(i->oprnd2(),i);
1408                                 }
1409                                 else if (i->isCall()) {
1410                                         for (int j=0, c=i->argc(); j < c; j++)
1411                                                 live.add(i->arg(j),i);
1412                                 }
1413                         }
1414                 }
1415
1416                 assm->outputf("live instruction count %ld, total %ld, max pressure %d",
1417                         live.retired.size(), total, live.maxlive);
1418         assm->outputf("side exits %ld", exits);
1419
1420                 // print live exprs, going forwards
1421                 LirNameMap *names = frag->lirbuf->names;
1422                 for (int j=live.retired.size()-1; j >= 0; j--)
1423         {
1424             RetiredEntry *e = live.retired[j];
1425             char livebuf[1000], *s=livebuf;
1426             *s = 0;
1427             for (int k=0,n=e->live.size(); k < n; k++) {
1428                                 strcpy(s, names->formatRef(e->live[k]));
1429                                 s += strlen(s);
1430                                 *s++ = ' '; *s = 0;
1431                                 NanoAssert(s < livebuf+sizeof(livebuf));
1432             }
1433                         printf("%-60s %s\n", livebuf, names->formatIns(e->i));
1434                         if (e->i->isGuard())
1435                                 printf("\n");
1436                 }
1437         }
1438
1439     LabelMap::Entry::~Entry()
1440     {
1441         delete name;
1442     }
1443
1444     LirNameMap::Entry::~Entry()
1445     {
1446         delete name;
1447     }
1448
1449     LirNameMap::~LirNameMap()
1450     {
1451         Entry *e;
1452
1453         while ((e = names.removeLast()) != NULL) {
1454             delete e;
1455         }
1456     }
1457
1458         void LirNameMap::addName(LInsp i, Stringp name) {
1459                 if (!names.containsKey(i)) {
1460                         Entry *e = new (labels->core->gc) Entry(name);
1461                         names.put(i, e);
1462                 }
1463         }
1464         void LirNameMap::addName(LInsp i, const char *name) {
1465                 addName(i, labels->core->newString(name));
1466         }
1467
1468         void LirNameMap::copyName(LInsp i, const char *s, int suffix) {
1469                 char s2[200];
1470                 sprintf(s2,"%s%d", s,suffix);
1471                 addName(i, labels->core->newString(s2));
1472         }
1473
1474         void LirNameMap::formatImm(int32_t c, char *buf) {
1475                 if (c >= 10000 || c <= -10000)
1476                         sprintf(buf,"#%s",labels->format((void*)c));
1477         else
1478             sprintf(buf,"%d", c);
1479         }
1480
1481         const char* LirNameMap::formatRef(LIns *ref)
1482         {
1483                 char buffer[200], *buf=buffer;
1484                 buf[0]=0;
1485                 GC *gc = labels->core->gc;
1486                 if (names.containsKey(ref)) {
1487                         StringNullTerminatedUTF8 cname(gc, names.get(ref)->name);
1488                         strcat(buf, cname.c_str());
1489                 }
1490                 else if (ref->isconstq()) {
1491                         formatImm(uint32_t(ref->constvalq()>>32), buf);
1492                         buf += strlen(buf);
1493                         *buf++ = ':';
1494                         formatImm(uint32_t(ref->constvalq()), buf);
1495                 }
1496                 else if (ref->isconst()) {
1497                         formatImm(ref->constval(), buf);
1498                 }
1499                 else {
1500                         if (ref->isCall()) {
1501                                 copyName(ref, _functions[ref->fid()]._name, funccounts.add(ref->fid()));
1502                         } else {
1503                                 copyName(ref, lirNames[ref->opcode()], lircounts.add(ref->opcode()));
1504                         }
1505                         StringNullTerminatedUTF8 cname(gc, names.get(ref)->name);
1506                         strcat(buf, cname.c_str());
1507                 }
1508                 return labels->dup(buffer);
1509         }
1510
1511         const char* LirNameMap::formatIns(LIns* i)
1512         {
1513                 char sbuf[200];
1514                 char *s = sbuf;
1515                 if (!i->isStore() && !i->isGuard() && !i->isop(LIR_trace)) {
1516                         sprintf(s, "%s = ", formatRef(i));
1517                         s += strlen(s);
1518                 }
1519
1520                 LOpcode op = i->opcode();
1521                 switch(op)
1522                 {
1523                         case LIR_short:
1524                         case LIR_int:
1525                         {
1526                 sprintf(s, "%s", formatRef(i));
1527                                 break;
1528                         }
1529
1530                         case LIR_quad:
1531                         {
1532                                 int32_t *p = (int32_t*) (i-2);
1533                                 sprintf(s, "#%X:%X", p[1], p[0]);
1534                                 break;
1535                         }
1536
1537                         case LIR_loop:
1538                         case LIR_trace:
1539                                 sprintf(s, "%s", lirNames[op]);
1540                                 break;
1541
1542                         case LIR_fcall:
1543                         case LIR_call: {
1544                                 sprintf(s, "%s ( ", _functions[i->fid()]._name);
1545                                 for (int32_t j=i->argc()-1; j >= 0; j--) {
1546                                         s += strlen(s);
1547                                         sprintf(s, "%s ",formatRef(i->arg(j)));
1548                                 }
1549                                 s += strlen(s);
1550                                 sprintf(s, ")");
1551                                 break;
1552                         }
1553
1554                         case LIR_param:
1555                 sprintf(s, "%s %s", lirNames[op], gpn(i->imm8()));
1556                                 break;
1557
1558             case LIR_callh:
1559                         case LIR_neg:
1560                         case LIR_fneg:
1561                         case LIR_i2f:
1562                         case LIR_u2f:
1563                         case LIR_qlo:
1564                         case LIR_qhi:
1565             case LIR_ov:
1566             case LIR_cs:
1567                         case LIR_not:
1568                                 sprintf(s, "%s %s", lirNames[op], formatRef(i->oprnd1()));
1569                                 break;
1570
1571                         case LIR_x:
1572                         case LIR_xt:
1573                         case LIR_xf:
1574                                 formatGuard(i, s);
1575                                 break;
1576
1577                         case LIR_add:
1578                         case LIR_sub:
1579                         case LIR_mul:
1580                         case LIR_fadd:
1581                         case LIR_fsub:
1582                         case LIR_fmul:
1583                         case LIR_fdiv:
1584                         case LIR_and:
1585                         case LIR_or:
1586                         case LIR_xor:
1587                         case LIR_lsh:
1588                         case LIR_rsh:
1589                         case LIR_ush:
1590                         case LIR_eq:
1591                         case LIR_lt:
1592                         case LIR_le:
1593                         case LIR_gt:
1594                         case LIR_ge:
1595                         case LIR_ult:
1596                         case LIR_ule:
1597                         case LIR_ugt:
1598                         case LIR_uge:
1599                         case LIR_feq:
1600                         case LIR_flt:
1601                         case LIR_fle:
1602                         case LIR_fgt:
1603                         case LIR_fge:
1604                         case LIR_qjoin:
1605                                 sprintf(s, "%s %s, %s", lirNames[op],
1606                                         formatRef(i->oprnd1()),
1607                                         formatRef(i->oprnd2()));
1608                                 break;
1609
1610                         case LIR_cmov:
1611                 sprintf(s, "%s ? %s : %s",
1612                                         formatRef(i->oprnd1()),
1613                                         formatRef(i->oprnd2()->oprnd1()),
1614                                         formatRef(i->oprnd2()->oprnd2()));
1615                                 break;
1616
1617                         case LIR_ld:
1618                         case LIR_ldc:
1619                         case LIR_ldq:
1620                         case LIR_ldcb:
1621                                 sprintf(s, "%s %s[%s]", lirNames[op],
1622                                         formatRef(i->oprnd1()),
1623                                         formatRef(i->oprnd2()));
1624                                 break;
1625
1626                         case LIR_st:
1627             case LIR_sti:
1628                         case LIR_stq:
1629             case LIR_stqi:
1630                                 sprintf(s, "%s[%d] = %s",
1631                                         formatRef(i->oprnd2()),
1632                                         i->immdisp(),
1633                                         formatRef(i->oprnd1()));
1634                                 break;
1635
1636                         default:
1637                                 sprintf(s, "?");
1638                                 break;
1639                 }
1640                 return labels->dup(sbuf);
1641         }
1642
1643
1644 #endif
1645         CseFilter::CseFilter(LirWriter *out, GC *gc)
1646                 : LirWriter(out), exprs(gc) {}
1647
1648         LIns* CseFilter::insImm(int32_t imm)
1649         {
1650                 uint32_t k;
1651                 LInsp found = exprs.find32(imm, k);
1652                 if (found)
1653                         return found;
1654                 return exprs.add(out->insImm(imm), k);
1655         }
1656
1657         LIns* CseFilter::insImmq(uint64_t q)
1658         {
1659                 uint32_t k;
1660                 LInsp found = exprs.find64(q, k);
1661                 if (found)
1662                         return found;
1663                 return exprs.add(out->insImmq(q), k);
1664         }
1665
1666         LIns* CseFilter::ins1(LOpcode v, LInsp a)
1667         {
1668                 if (isCse(v)) {
1669                         NanoAssert(operandCount[v]==1);
1670                         uint32_t k;
1671                         LInsp found = exprs.find1(v, a, k);
1672                         if (found)
1673                                 return found;
1674                         return exprs.add(out->ins1(v,a), k);
1675                 }
1676                 return out->ins1(v,a);
1677         }
1678
1679         LIns* CseFilter::ins2(LOpcode v, LInsp a, LInsp b)
1680         {
1681                 if (isCse(v)) {
1682                         NanoAssert(operandCount[v]==2);
1683                         uint32_t k;
1684                         LInsp found = exprs.find2(v, a, b, k);
1685                         if (found)
1686                                 return found;
1687                         return exprs.add(out->ins2(v,a,b), k);
1688                 }
1689                 return out->ins2(v,a,b);
1690         }
1691
1692         LIns* CseFilter::insLoad(LOpcode v, LInsp base, LInsp disp)
1693         {
1694                 if (isCse(v)) {
1695                         NanoAssert(operandCount[v]==2);
1696                         uint32_t k;
1697                         LInsp found = exprs.find2(v, base, disp, k);
1698                         if (found)
1699                                 return found;
1700                         return exprs.add(out->insLoad(v,base,disp), k);
1701                 }
1702                 return out->insLoad(v,base,disp);
1703         }
1704
1705         LInsp CseFilter::insGuard(LOpcode v, LInsp c, SideExit *x)
1706         {
1707                 if (isCse(v)) {
1708                         // conditional guard
1709                         NanoAssert(operandCount[v]==1);
1710                         uint32_t k;
1711                         LInsp found = exprs.find1(v, c, k);
1712                         if (found)
1713                                 return 0;
1714                         return exprs.add(out->insGuard(v,c,x), k);
1715                 }
1716                 return out->insGuard(v, c, x);
1717         }
1718
1719         LInsp CseFilter::insCall(uint32_t fid, LInsp args[])
1720         {
1721                 const CallInfo *c = &_functions[fid];
1722                 if (c->_cse) {
1723                         uint32_t k;
1724             uint32_t argc = c->count_args();
1725                         LInsp found = exprs.findcall(fid, argc, args, k);
1726                         if (found)
1727                                 return found;
1728                         return exprs.add(out->insCall(fid, args), k);
1729                 }
1730                 return out->insCall(fid, args);
1731         }
1732
1733         CseReader::CseReader(LirFilter *in, LInsHashSet *exprs, const CallInfo *functions)
1734                 : LirFilter(in), exprs(exprs), functions(functions)
1735         {}
1736
1737         LInsp CseReader::read()
1738         {
1739                 LInsp i = in->read();
1740                 if (i) {
1741                         if (i->isCse(functions))
1742                                 exprs->replace(i);
1743                 }
1744                 return i;
1745         }
1746
1747     LIns* FASTCALL callArgN(LIns* i, uint32_t n)
1748         {
1749                 return i->arg(i->argc()-n-1);
1750         }
1751
1752     void compile(Assembler* assm, Fragment* triggerFrag)
1753     {
1754         Fragmento *frago = triggerFrag->lirbuf->_frago;
1755         AvmCore *core = frago->core();
1756         GC *gc = core->gc;
1757
1758                 verbose_only( StringList asmOutput(gc); )
1759                 verbose_only( assm->_outputCache = &asmOutput; )
1760
1761                 verbose_only(if (assm->_verbose && core->config.verbose_live)
1762                         live(gc, assm, triggerFrag);)
1763
1764                 bool treeCompile = core->config.tree_opt && (triggerFrag->kind == BranchTrace);
1765                 RegAllocMap regMap(gc);
1766                 NInsList loopJumps(gc);
1767 #ifdef MEMORY_INFO
1768                 loopJumps.set_meminfo_name("LIR loopjumps");
1769 #endif
1770                 assm->beginAssembly(triggerFrag, &regMap);
1771
1772                 //fprintf(stderr, "recompile trigger %X kind %d\n", (int)triggerFrag, triggerFrag->kind);
1773                 Fragment* root = triggerFrag;
1774                 if (treeCompile)
1775                 {
1776                         // recompile the entire tree
1777                         root = triggerFrag->root;
1778                         root->removeIntraLinks();
1779                         root->unlink(assm);                     // unlink all incoming jumps ; since the compile() can fail
1780                         root->unlinkBranches(assm); // no one jumps into a branch (except from within the tree) so safe to clear the links table
1781                         root->fragEntry = 0;
1782                         root->releaseCode(frago);
1783
1784                         // do the tree branches
1785                         Fragment* frag = root->treeBranches;
1786                         while(frag)
1787                         {
1788                                 // compile til no more frags
1789                                 if (frag->lastIns)
1790                                 {
1791                                         assm->assemble(frag, loopJumps);
1792                                         verbose_only(if (assm->_verbose)
1793                                                 assm->outputf("compiling branch %s ip %s",
1794                                                         frago->labels->format(frag),
1795                                                         frago->labels->format(frag->ip)); )
1796
1797                                         NanoAssert(frag->kind == BranchTrace);
1798                                         RegAlloc* regs = new (gc) RegAlloc();
1799                                         assm->copyRegisters(regs);
1800                                         assm->releaseRegisters();
1801                                         SideExit* exit = frag->spawnedFrom->exit();
1802                                         regMap.put(exit, regs);
1803                                 }
1804                                 frag = frag->treeBranches;
1805                         }
1806                 }
1807
1808                 // now the the main trunk
1809                 assm->assemble(root, loopJumps);
1810                 verbose_only(if (assm->_verbose)
1811                         assm->outputf("compiling trunk %s",
1812                                 frago->labels->format(root));)
1813                 assm->endAssembly(root, loopJumps);
1814
1815                 // reverse output so that assembly is displayed low-to-high
1816                 verbose_only( assm->_outputCache = 0; )
1817                 verbose_only(for(int i=asmOutput.size()-1; i>=0; --i) { assm->outputf("%s",asmOutput.get(i)); } );
1818
1819                 if (assm->error())
1820                 {
1821                         root->fragEntry = 0;
1822                 }
1823                 else
1824                 {
1825                         root->link(assm);
1826                         if (treeCompile) root->linkBranches(assm);
1827                 }
1828
1829 #if defined(NJ_VERBOSE)
1830         for (size_t i = 0; i < asmOutput.size(); i++) {
1831             gc->Free(asmOutput.get(i));
1832         }
1833 #endif
1834     }
1835
1836         #endif /* FEATURE_NANOJIT */
1837
1838 #if defined(NJ_VERBOSE)
1839     LabelMap::LabelMap(AvmCore *core, LabelMap* parent)
1840         : parent(parent), names(core->gc), addrs(core->config.verbose_addrs), end(buf), core(core)
1841         {}
1842
1843     LabelMap::~LabelMap()
1844     {
1845         Entry *e;
1846
1847         while ((e = names.removeLast()) != NULL) {
1848             delete e;
1849         }
1850     }
1851
1852     void LabelMap::add(const void *p, size_t size, size_t align, const char *name)
1853         {
1854                 if (!this || names.containsKey(p))
1855                         return;
1856                 add(p, size, align, core->newString(name));
1857         }
1858
1859     void LabelMap::add(const void *p, size_t size, size_t align, Stringp name)
1860     {
1861                 if (!this || names.containsKey(p))
1862                         return;
1863                 Entry *e = new (core->gc) Entry(name, size<<align, align);
1864                 names.put(p, e);
1865     }
1866
1867     const char *LabelMap::format(const void *p)
1868     {
1869                 char b[200];
1870                 int i = names.findNear(p);
1871                 if (i >= 0) {
1872                         const void *start = names.keyAt(i);
1873                         Entry *e = names.at(i);
1874                         const void *end = (const char*)start + e->size;
1875                         avmplus::StringNullTerminatedUTF8 cname(core->gc, e->name);
1876                         const char *name = cname.c_str();
1877                         if (p == start) {
1878                                 if (addrs)
1879                                         sprintf(b,"%p %s",p,name);
1880                                 else
1881                                         strcpy(b, name);
1882                                 return dup(b);
1883                         }
1884                         else if (p > start && p < end) {
1885                                 int d = (intptr_t(p)-intptr_t(start)) >> e->align;
1886                                 if (addrs)
1887                                         sprintf(b, "%p %s+%d", p, name, d);
1888                                 else
1889                                         sprintf(b,"%s+%d", name, d);
1890                                 return dup(b);
1891                         }
1892                         else {
1893                                 if (parent)
1894                                         return parent->format(p);
1895
1896                                 sprintf(b, "%p", p);
1897                                 return dup(b);
1898                         }
1899                 }
1900                 if (parent)
1901                         return parent->format(p);
1902
1903                 sprintf(b, "%p", p);
1904                 return dup(b);
1905     }
1906
1907         const char *LabelMap::dup(const char *b)
1908         {
1909                 int need = strlen(b)+1;
1910                 char *s = end;
1911                 end += need;
1912                 if (end > buf+sizeof(buf)) {
1913                         s = buf;
1914                         end = s+need;
1915                 }
1916                 strcpy(s, b);
1917                 return s;
1918         }
1919
1920         // copy all labels to parent, adding newbase to label addresses
1921         void LabelMap::promoteAll(const void *newbase)
1922         {
1923                 for (int i=0, n=names.size(); i < n; i++) {
1924                         void *base = (char*)newbase + (intptr_t)names.keyAt(i);
1925                         parent->names.put(base, names.at(i));
1926                 }
1927         }
1928 #endif // NJ_VERBOSE
1929 }
1930