hphp/runtime/vm/jit/dce.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/vm/jit/dce.h"
  18
  19 #include <array>
  20 #include <folly/MapUtil.h>
  21
  22 #include "hphp/util/low-ptr.h"
  23 #include "hphp/util/match.h"
  24 #include "hphp/util/trace.h"
  25
  26 #include "hphp/runtime/vm/runtime.h"
  27 #include "hphp/runtime/vm/jit/analysis.h"
  28 #include "hphp/runtime/vm/jit/cfg.h"
  29 #include "hphp/runtime/vm/jit/check.h"
  30 #include "hphp/runtime/vm/jit/id-set.h"
  31 #include "hphp/runtime/vm/jit/ir-opcode.h"
  32 #include "hphp/runtime/vm/jit/ir-unit.h"
  33 #include "hphp/runtime/vm/jit/mutation.h"
  34 #include "hphp/runtime/vm/jit/memory-effects.h"
  35 #include "hphp/runtime/vm/jit/opt.h"
  36 #include "hphp/runtime/vm/jit/print.h"
  37 #include "hphp/runtime/vm/jit/simple-propagation.h"
  38 #include "hphp/runtime/vm/jit/state-vector.h"
  39 #include "hphp/runtime/vm/jit/timer.h"
  40 #include "hphp/runtime/vm/jit/translator-inline.h"
  41
  42 namespace HPHP { namespace jit {
  43 namespace {
  44
  45 TRACE_SET_MOD(hhir_dce);
  46
  47 bool canDCE(IRInstruction* inst) {
  48   switch (inst->op()) {
  49   case AssertNonNull:
  50   case AssertType:
  51   case AbsDbl:
  52   case AddInt:
  53   case SubInt:
  54   case MulInt:
  55   case AndInt:
  56   case AddDbl:
  57   case SubDbl:
  58   case MulDbl:
  59   case Sqrt:
  60   case OrInt:
  61   case XorInt:
  62   case Shl:
  63   case Shr:
  64   case Lshr:
  65   case Floor:
  66   case Ceil:
  67   case XorBool:
  68   case Mod:
  69   case ConvBoolToArr:
  70   case ConvDblToArr:
  71   case ConvIntToArr:
  72   case ConvFuncToArr:
  73   case ConvArrToBool:
  74   case ConvDblToBool:
  75   case ConvIntToBool:
  76   case ConvStrToBool:
  77   case ConvArrToDbl:
  78   case ConvBoolToDbl:
  79   case ConvIntToDbl:
  80   case ConvStrToDbl:
  81   case ConvResToDbl:
  82   case ConvBoolToInt:
  83   case ConvDblToInt:
  84   case ConvStrToInt:
  85   case ConvResToInt:
  86   case ConvDblToStr:
  87   case ConvIntToStr:
  88   case DblAsBits:
  89   case ConvPtrToLval:
  90   case NewColFromArray:
  91   case GtInt:
  92   case GteInt:
  93   case LtInt:
  94   case LteInt:
  95   case EqInt:
  96   case NeqInt:
  97   case CmpInt:
  98   case GtDbl:
  99   case GteDbl:
 100   case LtDbl:
 101   case LteDbl:
 102   case EqDbl:
 103   case NeqDbl:
 104   case CmpDbl:
 105   case GtStr:
 106   case GteStr:
 107   case LtStr:
 108   case LteStr:
 109   case EqStr:
 110   case NeqStr:
 111   case SameStr:
 112   case NSameStr:
 113   case CmpStr:
 114   case GtStrInt:
 115   case GteStrInt:
 116   case LtStrInt:
 117   case LteStrInt:
 118   case EqStrInt:
 119   case NeqStrInt:
 120   case CmpStrInt:
 121   case GtBool:
 122   case GteBool:
 123   case LtBool:
 124   case LteBool:
 125   case EqBool:
 126   case NeqBool:
 127   case CmpBool:
 128   case SameObj:
 129   case NSameObj:
 130   case EqKeyset:
 131   case NeqKeyset:
 132   case SameKeyset:
 133   case NSameKeyset:
 134   case GtRes:
 135   case GteRes:
 136   case LtRes:
 137   case LteRes:
 138   case EqRes:
 139   case NeqRes:
 140   case CmpRes:
 141   case EqRecDesc:
 142   case EqCls:
 143   case EqFunc:
 144   case EqStrPtr:
 145   case EqArrayDataPtr:
 146   case InstanceOf:
 147   case InstanceOfIface:
 148   case InstanceOfIfaceVtable:
 149   case ExtendsClass:
 150   case InstanceOfBitmask:
 151   case NInstanceOfBitmask:
 152   case InstanceOfRecDesc:
 153   case InterfaceSupportsArr:
 154   case InterfaceSupportsVec:
 155   case InterfaceSupportsDict:
 156   case InterfaceSupportsKeyset:
 157   case InterfaceSupportsStr:
 158   case InterfaceSupportsInt:
 159   case InterfaceSupportsDbl:
 160   case HasToString:
 161   case IsType:
 162   case IsNType:
 163   case IsTypeMem:
 164   case IsNTypeMem:
 165   case IsWaitHandle:
 166   case IsCol:
 167   case LdStk:
 168   case LdLoc:
 169   case LdStkAddr:
 170   case LdLocAddr:
 171   case LdRDSAddr:
 172   case LdMem:
 173   case LdContField:
 174   case LdClsInitElem:
 175   case LdIterBase:
 176   case LdIterPos:
 177   case LdIterEnd:
 178   case LdFrameThis:
 179   case LdFrameCls:
 180   case LdSmashable:
 181   case LdSmashableFunc:
 182   case LdClsFromClsMeth:
 183   case LdFuncFromClsMeth:
 184   case LdRecDesc:
 185   case DefConst:
 186   case Conjure:
 187   case LdClsInitData:
 188   case LookupClsRDS:
 189   case LdClsMethodCacheCls:
 190   case LdFuncVecLen:
 191   case LdClsMethod:
 192   case LdIfaceMethod:
 193   case LdPropAddr:
 194   case LdObjClass:
 195   case LdClsName:
 196   case LdARNumParams:
 197   case LdFuncCls:
 198   case LdFuncNumParams:
 199   case LdFuncName:
 200   case LdMethCallerName:
 201   case LdStrLen:
 202   case LdVecElem:
 203   case LdPackedElem:
 204   case LdPackedArrayDataElemAddr:
 205   case NewInstanceRaw:
 206   case NewArray:
 207   case NewMixedArray:
 208   case NewDArray:
 209   case NewDictArray:
 210   case NewLikeArray:
 211   case NewCol:
 212   case NewPair:
 213   case DefCallFlags:
 214   case DefCallFunc:
 215   case DefCallNumArgs:
 216   case DefCallCtx:
 217   case DefInlineFP:
 218   case LdRetVal:
 219   case Mov:
 220   case CountArray:
 221   case CountArrayFast:
 222   case CountVec:
 223   case CountDict:
 224   case CountKeyset:
 225   case CountCollection:
 226   case Nop:
 227   case AKExistsArr:
 228   case AKExistsDict:
 229   case AKExistsKeyset:
 230   case LdBindAddr:
 231   case LdSwitchDblIndex:
 232   case LdSwitchStrIndex:
 233   case LdSSwitchDestFast:
 234   case LdClosureCls:
 235   case LdClosureThis:
 236   case CreateSSWH:
 237   case LdContActRec:
 238   case LdContArValue:
 239   case LdContArKey:
 240   case LdWHState:
 241   case LdWHResult:
 242   case LdWHNotDone:
 243   case LdAFWHActRec:
 244   case LdMIPropStateAddr:
 245   case LdMIStateAddr:
 246   case StringIsset:
 247   case ColIsEmpty:
 248   case ColIsNEmpty:
 249   case LdUnwinderValue:
 250   case LdColVec:
 251   case LdColDict:
 252   case OrdStr:
 253   case ChrInt:
 254   case CheckRange:
 255   case LdMBase:
 256   case MethodExists:
 257   case LdTVAux:
 258   case ArrayIdx:
 259   case ArrayIsset:
 260   case DictGetQuiet:
 261   case DictGetK:
 262   case DictIsset:
 263   case DictIdx:
 264   case KeysetGetQuiet:
 265   case KeysetGetK:
 266   case KeysetIsset:
 267   case KeysetIdx:
 268   case VecFirst:
 269   case VecLast:
 270   case DictFirst:
 271   case DictFirstKey:
 272   case DictLast:
 273   case DictLastKey:
 274   case KeysetFirst:
 275   case KeysetLast:
 276   case GetTime:
 277   case GetTimeNs:
 278   case Select:
 279   case LdARFlags:
 280   case FuncHasAttr:
 281   case IsFunReifiedGenericsMatched:
 282   case IsClsDynConstructible:
 283   case LdFuncRxLevel:
 284   case StrictlyIntegerConv:
 285   case SetLegacyDict:
 286   case SetLegacyVec:
 287   case GetMemoKeyScalar:
 288   case LookupSPropSlot:
 289   case ConstructClosure:
 290   case AllocPackedArray:
 291   case AllocStructArray:
 292   case AllocStructDArray:
 293   case AllocStructDict:
 294   case AllocVArray:
 295   case AllocVecArray:
 296   case GetMixedPtrIter:
 297   case GetPackedPtrIter:
 298   case AdvanceMixedPtrIter:
 299   case AdvancePackedPtrIter:
 300   case LdPtrIterKey:
 301   case LdPtrIterVal:
 302   case EqPtrIter:
 303     assertx(!inst->isControlFlow());
 304     return true;
 305
 306   // These may raise oom, but its still ok to delete them if the
 307   // result is unused
 308   case ConcatIntStr:
 309   case ConcatStrInt:
 310   case ConcatStrStr:
 311   case ConcatStr3:
 312   case ConcatStr4:
 313   case AddNewElem:
 314   case AddNewElemKeyset:
 315   case AddNewElemVec:
 316     return true;
 317
 318   // Some of these conversion functions can run arbitrary PHP code.
 319   case ConvObjToArr:
 320   case ConvTVToArr:
 321   case ConvStrToArr:
 322   case ConvVecToArr:
 323   case ConvDictToArr:
 324   case ConvKeysetToArr:
 325   case ConvArrToNonDVArr:
 326   case ConvObjToDbl:
 327   case ConvTVToDbl:
 328   case ConvObjToInt:
 329   case ConvTVToInt:
 330   case ConvTVToBool:
 331   case ConvObjToBool:
 332   case ConvObjToStr:
 333   case ConvResToStr:
 334   case ConvTVToStr:
 335   case ConvArrToVec:
 336   case ConvDictToVec:
 337   case ConvKeysetToVec:
 338   case ConvObjToVec:
 339   case ConvArrToDict:
 340   case ConvVecToDict:
 341   case ConvKeysetToDict:
 342   case ConvObjToDict:
 343   case ConvArrToKeyset:
 344   case ConvVecToKeyset:
 345   case ConvDictToKeyset:
 346   case ConvObjToKeyset:
 347   case ConvArrToVArr:
 348   case ConvVecToVArr:
 349   case ConvDictToVArr:
 350   case ConvKeysetToVArr:
 351   case ConvObjToVArr:
 352   case ConvArrToDArr:
 353   case ConvVecToDArr:
 354   case ConvDictToDArr:
 355   case ConvKeysetToDArr:
 356   case ConvObjToDArr:
 357   case LdOutAddr:
 358     return !opcodeMayRaise(inst->op()) &&
 359       (!inst->consumesReferences() || inst->producesReference());
 360
 361   case ConvClsMethToArr:
 362   case ConvClsMethToDArr:
 363   case ConvClsMethToDict:
 364   case ConvClsMethToKeyset:
 365   case ConvClsMethToVArr:
 366   case ConvClsMethToVec: {
 367     bool consumeRef = use_lowptr ? false : inst->consumesReferences();
 368     return !opcodeMayRaise(inst->op()) &&
 369       (!consumeRef || inst->producesReference());
 370   }
 371
 372   case DbgTraceCall:
 373   case AKExistsObj:
 374   case StStk:
 375   case StOutValue:
 376   case CheckIter:
 377   case CheckType:
 378   case CheckNullptr:
 379   case CheckTypeMem:
 380   case CheckVArray:
 381   case CheckDArray:
 382   case CheckDVArray:
 383   case CheckMixedArrayKeys:
 384   case CheckSmashableClass:
 385   case CheckLoc:
 386   case CheckStk:
 387   case CheckMBase:
 388   case AssertLoc:
 389   case AssertStk:
 390   case AssertMBase:
 391   case CheckInit:
 392   case CheckInitMem:
 393   case CheckCold:
 394   case CheckInOuts:
 395   case EndGuards:
 396   case CheckNonNull:
 397   case DivDbl:
 398   case DivInt:
 399   case AddIntO:
 400   case SubIntO:
 401   case MulIntO:
 402
 403   case GtObj:
 404   case GteObj:
 405   case LtObj:
 406   case LteObj:
 407   case EqObj:
 408   case NeqObj:
 409   case CmpObj:
 410   case GtArr:
 411   case GteArr:
 412   case LtArr:
 413   case LteArr:
 414   case EqArr:
 415   case NeqArr:
 416   case CmpArr:
 417   case GtVec:
 418   case GteVec:
 419   case LtVec:
 420   case LteVec:
 421   case EqVec:
 422   case NeqVec:
 423   case CmpVec:
 424   case EqDict:
 425   case NeqDict:
 426   case JmpZero:
 427   case JmpNZero:
 428   case JmpSSwitchDest:
 429   case JmpSwitchDest:
 430   case ProfileSwitchDest:
 431   case CheckSurpriseFlags:
 432   case CheckSurpriseAndStack:
 433   case HandleRequestSurprise:
 434   case ReturnHook:
 435   case SuspendHookAwaitEF:
 436   case SuspendHookAwaitEG:
 437   case SuspendHookAwaitR:
 438   case SuspendHookCreateCont:
 439   case SuspendHookYield:
 440   case EndBlock:
 441   case Unreachable:
 442   case Jmp:
 443   case DefLabel:
 444   case LdLocPseudoMain:
 445   case LdPairElem:
 446   case DefCls:
 447   case LdClsCtor:
 448   case LdCls:
 449   case LdClsCached:
 450   case LdClsCachedSafe:
 451   case LdClsTypeCns:
 452   case LdClsTypeCnsClsName:
 453   case LdRecDescCached:
 454   case LdRecDescCachedSafe:
 455   case LdCns:
 456   case LookupCnsE:
 457   case LdClsCns:
 458   case InitClsCns:
 459   case LdSubClsCns:
 460   case LdSubClsCnsClsName:
 461   case LdTypeCns:
 462   case CheckSubClsCns:
 463   case LdClsCnsVecLen:
 464   case LookupClsMethodFCache:
 465   case LookupClsMethodCache:
 466   case LookupClsMethod:
 467   case LdGblAddr:
 468   case LdGblAddrDef:
 469   case LdClsPropAddrOrNull:
 470   case LdClsPropAddrOrRaise:
 471   case LdInitRDSAddr:
 472   case LdInitPropAddr:
 473   case LdObjMethodD:
 474   case LdObjMethodS:
 475   case LdObjInvoke:
 476   case LdFunc:
 477   case LdFuncCached:
 478   case LookupFuncCached:
 479   case AllocObj:
 480   case AllocObjReified:
 481   case NewClsMeth:
 482   case FuncCred:
 483   case InitProps:
 484   case PropTypeRedefineCheck:
 485   case InitSProps:
 486   case InitObjProps:
 487   case InitObjMemoSlots:
 488   case LockObj:
 489   case DebugBacktrace:
 490   case DebugBacktraceFast:
 491   case InitThrowableFileAndLine:
 492   case ConstructInstance:
 493   case InitMixedLayoutArray:
 494   case InitPackedLayoutArray:
 495   case InitPackedLayoutArrayLoop:
 496   case NewKeysetArray:
 497   case NewRecord:
 498   case NewRecordArray:
 499   case NewStructArray:
 500   case NewStructDArray:
 501   case NewStructDict:
 502   case Clone:
 503   case InlineReturn:
 504   case InlineSuspend:
 505   case CallUnpack:
 506   case Call:
 507   case NativeImpl:
 508   case CallBuiltin:
 509   case RetCtrl:
 510   case AsyncFuncRet:
 511   case AsyncFuncRetSlow:
 512   case AsyncSwitchFast:
 513   case ReleaseVVAndSkip:
 514   case GenericRetDecRefs:
 515   case StClsInitElem:
 516   case StMem:
 517   case StIterBase:
 518   case StIterType:
 519   case StIterEnd:
 520   case StIterPos:
 521   case StLoc:
 522   case StLocPseudoMain:
 523   case StLocRange:
 524   case EagerSyncVMRegs:
 525   case ReqBindJmp:
 526   case ReqRetranslate:
 527   case ReqRetranslateOpt:
 528   case IncRef:
 529   case DecRef:
 530   case DecRefNZ:
 531   case ProfileDecRef:
 532   case DefFP:
 533   case DefFuncEntryFP:
 534   case DefFrameRelSP:
 535   case DefRegSP:
 536   case Count:
 537   case VerifyParamCls:
 538   case VerifyParamCallable:
 539   case VerifyParamFail:
 540   case VerifyParamFailHard:
 541   case VerifyReifiedLocalType:
 542   case VerifyReifiedReturnType:
 543   case VerifyRetCallable:
 544   case VerifyRetCls:
 545   case VerifyRetFail:
 546   case VerifyRetFailHard:
 547   case VerifyProp:
 548   case VerifyPropCls:
 549   case VerifyPropCoerce:
 550   case VerifyPropFail:
 551   case VerifyPropFailHard:
 552   case VerifyParamRecDesc:
 553   case VerifyRetRecDesc:
 554   case VerifyPropRecDesc:
 555   case RaiseClsMethPropConvertNotice:
 556   case RaiseHackArrParamNotice:
 557   case RaiseHackArrPropNotice:
 558   case RaiseUninitLoc:
 559   case RaiseUndefProp:
 560   case RaiseTooManyArg:
 561   case RaiseError:
 562   case RaiseErrorOnInvalidIsAsExpressionType:
 563   case RaiseWarning:
 564   case RaiseNotice:
 565   case ThrowArrayIndexException:
 566   case ThrowArrayKeyException:
 567   case RaiseArraySerializeNotice:
 568   case RaiseHackArrCompatNotice:
 569   case RaiseForbiddenDynCall:
 570   case RaiseForbiddenDynConstruct:
 571   case RaiseRxCallViolation:
 572   case RaiseStrToClassNotice:
 573   case CheckClsReifiedGenericMismatch:
 574   case CheckFunReifiedGenericMismatch:
 575   case PrintStr:
 576   case PrintInt:
 577   case PrintBool:
 578   case ArrayAdd:
 579   case GetMemoKey:
 580   case LdSwitchObjIndex:
 581   case LdSSwitchDestSlow:
 582   case InterpOne:
 583   case InterpOneCF:
 584   case OODeclExists:
 585   case StClosureArg:
 586   case CreateGen:
 587   case CreateAGen:
 588   case CreateAAWH:
 589   case CreateAFWH:
 590   case CreateAFWHNoVV:
 591   case CreateAGWH:
 592   case AFWHPrepareChild:
 593   case StArResumeAddr:
 594   case ContEnter:
 595   case ContPreNext:
 596   case ContStartedCheck:
 597   case ContValid:
 598   case ContStarted:
 599   case ContArIncKey:
 600   case ContArIncIdx:
 601   case ContArUpdateIdx:
 602   case LdContResumeAddr:
 603   case StContArState:
 604   case StContArValue:
 605   case StContArKey:
 606   case AFWHBlockOn:
 607   case AFWHPushTailFrame:
 608   case CountWHNotDone:
 609   case IncStat:
 610   case IncProfCounter:
 611   case DbgAssertRefCount:
 612   case DbgAssertFunc:
 613   case DbgCheckLocalsDecRefd:
 614   case RBTraceEntry:
 615   case RBTraceMsg:
 616   case ZeroErrorLevel:
 617   case RestoreErrorLevel:
 618   case IterInit:
 619   case IterInitK:
 620   case LIterInit:
 621   case LIterInitK:
 622   case IterNext:
 623   case IterNextK:
 624   case LIterNext:
 625   case LIterNextK:
 626   case IterFree:
 627   case KillIter:
 628   case BaseG:
 629   case PropX:
 630   case PropQ:
 631   case PropDX:
 632   case CGetProp:
 633   case CGetPropQ:
 634   case SetProp:
 635   case UnsetProp:
 636   case SetOpProp:
 637   case IncDecProp:
 638   case IssetProp:
 639   case ElemX:
 640   case ProfileMixedArrayAccess:
 641   case CheckMixedArrayOffset:
 642   case CheckArrayCOW:
 643   case ProfileDictAccess:
 644   case CheckDictOffset:
 645   case ProfileKeysetAccess:
 646   case CheckKeysetOffset:
 647   case ElemArrayX:
 648   case ElemArrayD:
 649   case ElemArrayU:
 650   case ElemMixedArrayK:
 651   case ElemVecD:
 652   case ElemVecU:
 653   case ElemDictX:
 654   case ElemDictD:
 655   case ElemDictU:
 656   case ElemDictK:
 657   case ElemKeysetX:
 658   case ElemKeysetU:
 659   case ElemKeysetK:
 660   case ElemDX:
 661   case ElemUX:
 662   case ArrayGet:
 663   case MixedArrayGetK:
 664   case DictGet:
 665   case KeysetGet:
 666   case StringGet:
 667   case OrdStrIdx:
 668   case MapGet:
 669   case CGetElem:
 670   case ArraySet:
 671   case VecSet:
 672   case DictSet:
 673   case MapSet:
 674   case VectorSet:
 675   case SetElem:
 676   case SetRange:
 677   case SetRangeRev:
 678   case UnsetElem:
 679   case SetOpElem:
 680   case IncDecElem:
 681   case SetNewElem:
 682   case SetNewElemArray:
 683   case SetNewElemVec:
 684   case SetNewElemKeyset:
 685   case ReservePackedArrayDataNewElem:
 686   case VectorIsset:
 687   case PairIsset:
 688   case MapIsset:
 689   case IssetElem:
 690   case ProfileArrayKind:
 691   case ProfileType:
 692   case ProfileCall:
 693   case ProfileMethod:
 694   case ProfileSubClsCns:
 695   case CheckPackedArrayDataBounds:
 696   case LdVectorSize:
 697   case BeginCatch:
 698   case EndCatch:
 699   case EnterTCUnwind:
 700   case UnwindCheckSideExit:
 701   case DbgTrashStk:
 702   case DbgTrashFrame:
 703   case DbgTrashMem:
 704   case DbgTrashRetVal:
 705   case EnterPrologue:
 706   case CheckStackOverflow:
 707   case CheckSurpriseFlagsEnter:
 708   case JmpPlaceholder:
 709   case ThrowOutOfBounds:
 710   case ThrowInvalidArrayKey:
 711   case ThrowInvalidOperation:
 712   case ThrowCallReifiedFunctionWithoutGenerics:
 713   case ThrowDivisionByZeroException:
 714   case ThrowHasThisNeedStatic:
 715   case ThrowLateInitPropError:
 716   case ThrowMissingArg:
 717   case ThrowMissingThis:
 718   case ThrowParameterWrongType:
 719   case ThrowParamInOutMismatch:
 720   case ThrowParamInOutMismatchRange:
 721   case StMBase:
 722   case StMIPropState:
 723   case FinishMemberOp:
 724   case InlineReturnNoFrame:
 725   case BeginInlining:
 726   case SyncReturnBC:
 727   case SetOpTV:
 728   case SetOpTVVerify:
 729   case ConjureUse:
 730   case LdClsMethodFCacheFunc:
 731   case LdClsMethodCacheFunc:
 732   case ProfileInstanceCheck:
 733   case MemoGetStaticValue:
 734   case MemoGetStaticCache:
 735   case MemoGetLSBValue:
 736   case MemoGetLSBCache:
 737   case MemoGetInstanceValue:
 738   case MemoGetInstanceCache:
 739   case MemoSetStaticValue:
 740   case MemoSetStaticCache:
 741   case MemoSetLSBValue:
 742   case MemoSetLSBCache:
 743   case MemoSetInstanceValue:
 744   case MemoSetInstanceCache:
 745   case ThrowAsTypeStructException:
 746   case RecordReifiedGenericsAndGetTSList:
 747   case ResolveTypeStruct:
 748   case CheckRDSInitialized:
 749   case MarkRDSInitialized:
 750   case ProfileProp:
 751     return false;
 752
 753   case SameArr:
 754   case NSameArr:
 755   case SameVec:
 756   case NSameVec:
 757   case SameDict:
 758   case NSameDict:
 759     return
 760       !RuntimeOption::EvalHackArrCompatCheckCompare &&
 761       !RuntimeOption::EvalHackArrCompatDVCmpNotices;
 762
 763   case IsTypeStruct:
 764     return !opcodeMayRaise(IsTypeStruct);
 765   }
 766   not_reached();
 767 }
 768
 769 /* DceFlags tracks the state of one instruction during dead code analysis. */
 770 struct DceFlags {
 771   DceFlags()
 772     : m_state(DEAD)
 773     , m_weakUseCount(0)
 774   {}
 775
 776   bool isDead() const { return m_state == DEAD; }
 777   void setDead()      { m_state = DEAD; }
 778   void setLive()      { m_state = LIVE; }
 779
 780   /*
 781    * "Weak" uses are used in optimizeActRecs.
 782    *
 783    * If a frame pointer is used for something that can be modified to
 784    * not be a use as long as the whole frame can go away, we'll track
 785    * that here.
 786    */
 787   void incWeakUse() {
 788     if (m_weakUseCount + 1 > kMaxWeakUseCount) {
 789       // Too many weak uses for us to know we can optimize it away.
 790       return;
 791     }
 792     ++m_weakUseCount;
 793   }
 794
 795   int32_t weakUseCount() const {
 796     return m_weakUseCount;
 797   }
 798
 799   std::string toString() const {
 800     std::array<const char*,2> const names = {{
 801       "DEAD",
 802       "LIVE",
 803     }};
 804     return folly::format(
 805       "{}",
 806       m_state < names.size() ? names[m_state] : "<invalid>"
 807     ).str();
 808   }
 809
 810 private:
 811   enum {
 812     DEAD = 0,
 813     LIVE,
 814   };
 815   uint8_t m_state:1;
 816   static constexpr uint8_t kMaxWeakUseCount = 0x7f;
 817   uint8_t m_weakUseCount:7;
 818 };
 819 static_assert(sizeof(DceFlags) == 1, "sizeof(DceFlags) should be 1 byte");
 820
 821 // DCE state indexed by instr->id().
 822 typedef StateVector<IRInstruction, DceFlags> DceState;
 823 typedef StateVector<SSATmp, uint32_t> UseCounts;
 824 typedef jit::vector<IRInstruction*> WorkList;
 825
 826 void removeDeadInstructions(IRUnit& unit, const DceState& state) {
 827   postorderWalk(
 828     unit,
 829     [&](Block* block) {
 830       auto const next = block->next();
 831       auto const bcctx = block->back().bcctx();
 832       block->remove_if(
 833         [&] (const IRInstruction& inst) {
 834           ONTRACE(
 835             4,
 836             if (state[inst].isDead()) {
 837               FTRACE(1, "Removing dead instruction {}\n", inst.toString());
 838             }
 839           );
 840
 841           auto const dead = state[inst].isDead();
 842           assertx(!dead || !inst.taken() || inst.taken()->isCatch());
 843           return dead;
 844         }
 845       );
 846       if (block->empty() || !block->back().isBlockEnd()) {
 847         assertx(next);
 848         block->push_back(unit.gen(Jmp, bcctx, next));
 849       }
 850     }
 851   );
 852 }
 853
 854 // removeUnreachable erases unreachable blocks from unit, and returns
 855 // a sorted list of the remaining blocks.
 856 BlockList prepareBlocks(IRUnit& unit) {
 857   FTRACE(1, "RemoveUnreachable:vvvvvvvvvvvvvvvvvvvv\n");
 858   SCOPE_EXIT { FTRACE(1, "RemoveUnreachable:^^^^^^^^^^^^^^^^^^^^\n"); };
 859
 860   auto const blocks = rpoSortCfg(unit);
 861
 862   // 1. perform copy propagation on every instruction
 863   for (auto block : blocks) {
 864     for (auto& inst : *block) {
 865       copyProp(&inst);
 866     }
 867   }
 868
 869   // 2. erase unreachable blocks and get an rpo sorted list of what remains.
 870   bool needsReflow = removeUnreachable(unit);
 871
 872   // 3. if we removed any whole blocks that ended in Jmp instructions, reflow
 873   //    all types in case they change the incoming types of DefLabel
 874   //    instructions.
 875   if (needsReflow) reflowTypes(unit);
 876
 877   return blocks;
 878 }
 879
 880 WorkList initInstructions(const IRUnit& unit, const BlockList& blocks,
 881                           DceState& state) {
 882   TRACE(1, "DCE(initInstructions):vvvvvvvvvvvvvvvvvvvv\n");
 883   // Mark reachable, essential, instructions live and enqueue them.
 884   WorkList wl;
 885   wl.reserve(unit.numInsts());
 886   forEachInst(blocks, [&] (IRInstruction* inst) {
 887     if (!canDCE(inst)) {
 888       state[inst].setLive();
 889       wl.push_back(inst);
 890     }
 891   });
 892   TRACE(1, "DCE:^^^^^^^^^^^^^^^^^^^^\n");
 893   return wl;
 894 }
 895
 896 //////////////////////////////////////////////////////////////////////
 897
 898 /*
 899  * A use of an inlined frame that can be modified to work without the
 900  * frame is called a "weak use" here.  For example, storing to a local
 901  * on a frame is weak because if no other uses of the frame are
 902  * keeping it alive (for example a load of that same local), we can
 903  * just remove the store.
 904  *
 905  * This routine counts the weak uses of inlined frames and marks them
 906  * dead if they have no non-weak uses.  Returns true if any inlined
 907  * frames were marked dead.
 908  */
 909 bool findWeakActRecUses(const BlockList& blocks,
 910                         DceState& state,
 911                         IRUnit& unit,
 912                         const UseCounts& uses) {
 913   bool killedFrames = false;
 914
 915   auto const incWeak = [&] (const IRInstruction* inst, const SSATmp* src) {
 916     assertx(src->isA(TFramePtr));
 917     auto const frameInst = src->inst();
 918     if (frameInst->op() == DefInlineFP) {
 919       ITRACE(3, "weak use of {} from {}\n", *frameInst, *inst);
 920       state[frameInst].incWeakUse();
 921     }
 922   };
 923
 924   forEachInst(blocks, [&] (IRInstruction* inst) {
 925     if (state[inst].isDead()) return;
 926
 927     switch (inst->op()) {
 928     // these can be made stack relative
 929     case StLoc: {
 930       auto const id = inst->marker().func()->lookupVarId(s_86metadata.get());
 931       if (inst->extra<StLoc>()->locId != id) incWeak(inst, inst->src(0));
 932       break;
 933     }
 934     case LdLoc:
 935     case CheckLoc:
 936     case AssertLoc:
 937     case LdLocAddr:
 938       incWeak(inst, inst->src(0));
 939       break;
 940
 941     // These can be made stack relative if they haven't been already.
 942     case MemoGetStaticCache:
 943     case MemoSetStaticCache:
 944     case MemoGetLSBCache:
 945     case MemoSetLSBCache:
 946     case MemoGetInstanceCache:
 947     case MemoSetInstanceCache:
 948       if (inst->src(0)->isA(TFramePtr)) incWeak(inst, inst->src(0));
 949       break;
 950
 951     case InlineReturn:
 952       {
 953         auto const frameInst = inst->src(0)->inst();
 954         assertx(frameInst->is(DefInlineFP));
 955         auto const frameUses = uses[frameInst->dst()];
 956         auto const weakUses  = state[frameInst].weakUseCount();
 957         /*
 958          * We can kill the frame if all uses of the frame are counted
 959          * as weak uses.  Note that this InlineReturn counts as a weak
 960          * use, but we haven't incremented for it yet, which is where
 961          * the "+ 1" comes from below.
 962          */
 963         ITRACE(2, "frame {}: weak/strong {}/{}\n",
 964           *frameInst, weakUses, frameUses);
 965         if (frameUses - (weakUses + 1) == 0) {
 966           ITRACE(1, "killing frame {}\n", *frameInst);
 967           killedFrames = true;
 968           state[frameInst].setDead();
 969
 970           // Ensure that the frame is still dead for the purposes of
 971           // memory-effects
 972           convertToInlineReturnNoFrame(unit, *inst);
 973         }
 974       }
 975       break;
 976
 977     default:
 978       // Default is conservative: we don't increment a weak use if it
 979       // uses the frame (or stack), so they can't be eliminated.
 980       break;
 981     }
 982   });
 983
 984   return killedFrames;
 985 }
 986
 987 /*
 988  * Convert a localId in a callee frame into an SP relative offset in the caller
 989  * frame.
 990  */
 991 IRSPRelOffset locToStkOff(LocalId locId, const SSATmp* fp) {
 992   auto const fpInst = fp->inst();
 993   assertx(fpInst->is(DefInlineFP));
 994   return fpInst->extra<DefInlineFP>()->spOffset - locId.locId - 1;
 995 }
 996
 997 /*
 998  * The first time through, we've counted up weak uses of the frame and then
 999  * finally marked it dead.  The instructions in between that were weak uses may
1000  * need modifications now that their frame is going away.
1001  *
1002  * Also, if we eliminated some frames, DecRef instructions (which can re-enter
1003  * the VM without requiring a materialized frame) need to have stack depths in
1004  * their markers adjusted so they can't stomp on parts of the outer function.
1005  * We handle this conservatively by just pushing all DecRef markers where the
1006  * DecRef is from a function other than the outer function down to a safe
1007  * re-entry depth.
1008  *
1009  * Finally, any removed frame pointers in BCMarkers must be rewritten to point
1010  * to the outer frame of that frame.
1011  */
1012 void performActRecFixups(const BlockList& blocks,
1013                          DceState& state,
1014                          IRUnit& unit,
1015                          const UseCounts& uses) {
1016   // We limit the total stack depth during inlining, so this is the deepest
1017   // we'll ever have to worry about.
1018   auto const outerFunc = blocks.front()->front().marker().func();
1019   auto const safeDepth = outerFunc->maxStackCells() + kStackCheckLeafPadding;
1020   ITRACE(3, "safeDepth: {}, outerFunc depth: {}\n",
1021          safeDepth,
1022          outerFunc->maxStackCells());
1023
1024   bool needsReflow = false;
1025
1026   for (auto block : blocks) {
1027     ITRACE(2, "Visiting block {}\n", block->id());
1028     Trace::Indent indenter;
1029
1030     for (auto& inst : *block) {
1031       ITRACE(5, "{}\n", inst.toString());
1032
1033       bool adjustedMarkerFp = false;
1034       if (auto const fp = inst.marker().fp()) {
1035         if (state[fp->inst()].isDead()) {
1036           always_assert(fp->inst()->is(DefInlineFP));
1037           auto const prev = fp->inst()->src(1);
1038           inst.marker() = inst.marker().adjustFP(prev);
1039           assertx(!state[prev->inst()].isDead());
1040           adjustedMarkerFp = true;
1041         }
1042       }
1043
1044       switch (inst.op()) {
1045       case DefInlineFP:
1046         ITRACE(3, "DefInlineFP ({}): weak/strong uses: {}/{}\n",
1047              inst, state[inst].weakUseCount(), uses[inst.dst()]);
1048         break;
1049
1050       case StLoc:
1051       case LdLoc:
1052       case LdLocAddr:
1053       case AssertLoc:
1054       case CheckLoc:
1055         if (state[inst.src(0)->inst()].isDead()) {
1056           convertToStackInst(unit, inst);
1057           needsReflow = true;
1058         }
1059         break;
1060
1061       /*
1062        * These are special: they're the only instructions that can reenter
1063        * but not throw. This means it's safe to elide their inlined frame, as
1064        * long as we adjust their markers to a depth that is guaranteed to not
1065        * stomp on the caller's frame if it reenters.
1066        */
1067       case DecRef:
1068       case MemoSetStaticValue:
1069       case MemoSetLSBValue:
1070       case MemoSetInstanceValue:
1071         if (adjustedMarkerFp) {
1072           ITRACE(3, "pushing stack depth of {} to {}\n", safeDepth, inst);
1073           inst.marker() = inst.marker().adjustSP(FPInvOffset{safeDepth});
1074         }
1075         break;
1076
1077       case MemoGetStaticCache:
1078       case MemoGetLSBCache:
1079       case MemoGetInstanceCache:
1080         if (inst.src(0)->isA(TFramePtr) &&
1081             state[inst.src(0)->inst()].isDead()) {
1082           convertToStackInst(unit, inst);
1083         }
1084         break;
1085       case MemoSetStaticCache:
1086       case MemoSetLSBCache:
1087       case MemoSetInstanceCache:
1088         if (inst.src(0)->isA(TFramePtr) &&
1089             state[inst.src(0)->inst()].isDead()) {
1090           // For the same reason as above, we need to adjust the markers for
1091           // re-entracy.
1092           convertToStackInst(unit, inst);
1093           if (adjustedMarkerFp) {
1094             ITRACE(3, "pushing stack depth of {} to {}\n", safeDepth, inst);
1095             inst.marker() = inst.marker().adjustSP(FPInvOffset{safeDepth});
1096           }
1097         }
1098         break;
1099
1100       default:
1101         break;
1102       }
1103     }
1104   }
1105
1106   if (needsReflow) reflowTypes(unit);
1107 }
1108
1109 /*
1110  * Look for InlineReturn instructions that are the only "non-weak" use
1111  * of a DefInlineFP.  In this case we can kill both, avoiding the ActRec
1112  * spill.
1113  *
1114  * Prior to calling this routine, `uses' should contain the direct
1115  * (non-transitive) use counts of each DefInlineFP instruction.  If
1116  * the weak references are equal to the normal references, the
1117  * instruction is not necessary and can be removed (if we make the
1118  * required changes to each instruction that used it weakly).
1119  */
1120 void optimizeActRecs(const BlockList& blocks,
1121                      DceState& state,
1122                      IRUnit& unit,
1123                      const UseCounts& uses) {
1124   FTRACE(1, "AR:vvvvvvvvvvvvvvvvvvvvv\n");
1125   SCOPE_EXIT { FTRACE(1, "AR:^^^^^^^^^^^^^^^^^^^^^\n"); };
1126
1127   // Make a pass to find if we can kill any of the frames.  If so, we
1128   // have to do some fixups.  These two routines are coupled---most
1129   // cases in findWeakActRecUses should have a corresponding case in
1130   // performActRecFixups to deal with the frame being removed.
1131   auto const killedFrames = findWeakActRecUses(blocks, state, unit, uses);
1132   if (killedFrames) {
1133     ITRACE(1, "Killed some frames. Iterating over blocks for fixups.\n");
1134     performActRecFixups(blocks, state, unit, uses);
1135   }
1136 }
1137
1138 IRInstruction* resolveFpDefLabelImpl(
1139   const SSATmp* fp,
1140   IdSet<SSATmp>& visited
1141 ) {
1142   auto const inst = fp->inst();
1143   assertx(inst->is(DefLabel));
1144
1145   // We already examined this, avoid loops.
1146   if (visited[fp]) return nullptr;
1147
1148   auto const dests = inst->dsts();
1149   auto const destIdx =
1150     std::find(dests.begin(), dests.end(), fp) - dests.begin();
1151   always_assert(destIdx >= 0 && destIdx < inst->numDsts());
1152
1153   // If any of the inputs to the Phi aren't Phis themselves, then just choose
1154   // that.
1155   IRInstruction* outInst = nullptr;
1156   inst->block()->forEachSrc(
1157     destIdx,
1158     [&] (const IRInstruction*, const SSATmp* tmp) {
1159       if (outInst) return;
1160       auto const i = canonical(tmp)->inst();
1161       if (!i->is(DefLabel)) outInst = i;
1162     }
1163   );
1164   if (outInst) return outInst;
1165
1166   // Otherwise we need to recursively look at the linked Phis, avoiding visiting
1167   // this Phi again.
1168   visited.add(fp);
1169   inst->block()->forEachSrc(
1170     destIdx,
1171     [&] (const IRInstruction*, const SSATmp* tmp) {
1172       if (outInst) return;
1173       tmp = canonical(tmp);
1174       auto const DEBUG_ONLY label = tmp->inst();
1175       assertx(label->is(DefLabel));
1176       outInst = resolveFpDefLabelImpl(tmp, visited);
1177     }
1178   );
1179
1180   return outInst;
1181 }
1182
1183 //////////////////////////////////////////////////////////////////////
1184
1185 void processCatchBlock(IRUnit& unit, DceState& state, Block* block,
1186                        FPRelOffset stackTop, const UseCounts& uses) {
1187   using Bits = std::bitset<64>;
1188
1189   auto const stackSize = (stackTop.offset < -64) ? 64 : -stackTop.offset;
1190   if (stackSize == 0) return;
1191   auto const stackBase = stackTop + stackSize;
1192   // subtract 1 because we want the cells at offsets -1, -2, ... -stackSize
1193   auto const stackRange = AStack { stackBase - 1, stackSize };
1194
1195   Bits usedLocations = {};
1196   // stores that are only read by the EndCatch
1197   jit::fast_set<IRInstruction*> candidateStores;
1198   // Any IncRefs we see; if they correspond to stores above, we can
1199   // replace the store with a store of Null, and kill the IncRef.
1200   jit::fast_map<SSATmp*, std::vector<Block::iterator>> candidateIncRefs;
1201
1202   auto const range =
1203     [&] (const AliasClass& cls) -> std::pair<int, int> {
1204       if (!cls.maybe(stackRange)) return {};
1205       auto const stk = cls.stack();
1206       if (!stk) return { 0, stackSize };
1207       if (stk->offset < stackTop) {
1208         auto const delta = stackTop.offset - stk->offset.offset;
1209         if (delta >= stk->size) return {};
1210         return { 0, stk->size - delta };
1211       }
1212       auto const base = stk->offset.offset - stackTop.offset;
1213       if (base >= stackSize) return {};
1214       auto const end = base + stk->size < stackSize ?
1215         base + stk->size : stackSize;
1216       return { base, end };
1217     };
1218
1219   auto const process_stack =
1220     [&] (const AliasClass& cls) {
1221       auto r = range(cls);
1222       while (r.first < r.second) {
1223         usedLocations.set(r.first++);
1224       }
1225       return false;
1226     };
1227
1228   auto const do_store =
1229     [&] (const AliasClass& cls, IRInstruction* store) {
1230       if (!store->is(StStk)) return false;
1231       auto const stk = cls.is_stack();
1232       if (!stk) return process_stack(cls);
1233       auto const r = range(cls);
1234       if (r.first != r.second) {
1235         assertx(r.second == r.first + 1);
1236         if (!usedLocations.test(r.first)) {
1237           usedLocations.set(r.first);
1238           candidateStores.insert(store);
1239         }
1240       }
1241       return false;
1242     };
1243
1244   auto done = false;
1245   for (auto inst = block->end(); inst != block->begin(); ) {
1246     --inst;
1247     if (inst->is(EndCatch)) {
1248       continue;
1249     }
1250     if (inst->is(IncRef)) {
1251       candidateIncRefs[inst->src(0)].push_back(inst);
1252       continue;
1253     }
1254     if (done) continue;
1255     auto const effects = canonicalize(memory_effects(*inst));
1256     done = match<bool>(
1257       effects,
1258       [&] (IrrelevantEffects)    { return false; },
1259       [&] (UnknownEffects)       { return true; },
1260       [&] (ReturnEffects x)      { return true; },
1261       [&] (CallEffects x)        { return true; },
1262       [&] (GeneralEffects x)     {
1263         return
1264           process_stack(x.loads) ||
1265           process_stack(x.stores) ||
1266           process_stack(x.kills);
1267       },
1268       [&] (PureLoad x)           { return process_stack(x.src); },
1269       [&] (PureStore x)          { return do_store(x.dst, &*inst); },
1270       [&] (ExitEffects x)        { return process_stack(x.live); },
1271       [&] (InlineEnterEffects x) {
1272         return
1273           process_stack(x.inlStack) ||
1274           process_stack(x.actrec);
1275       },
1276       [&] (InlineExitEffects x)  { return process_stack(x.inlStack); }
1277     );
1278   }
1279
1280   for (auto store : candidateStores) {
1281     auto const src = store->src(1);
1282     auto const it = candidateIncRefs.find(src);
1283     if (it != candidateIncRefs.end()) {
1284       FTRACE(3, "Erasing {} for {}\n",
1285              it->second.back()->toString(), store->toString());
1286       block->erase(it->second.back());
1287       if (it->second.size() > 1) {
1288         it->second.pop_back();
1289       } else {
1290         candidateIncRefs.erase(it);
1291       }
1292     } else {
1293       auto const srcInst = src->inst();
1294       if (!srcInst->producesReference() ||
1295           !canDCE(srcInst) ||
1296           uses[src] != 1) {
1297         continue;
1298       }
1299       FTRACE(3, "Erasing {} for {}\n",
1300              srcInst->toString(), store->toString());
1301       state[srcInst].setDead();
1302     }
1303     store->setSrc(1, unit.cns(TInitNull));
1304   }
1305 }
1306
1307 /*
1308  * A store to the stack which is post-dominated by the EndCatch and
1309  * not otherwise read is only there to ensure the unwinder DecRefs the
1310  * value it contains. If there's also an IncRef of the value in the
1311  * catch trace we can just store InitNull to the stack location and
1312  * drop the IncRef (and later, maybe adjust the sp of the
1313  * catch-trace's owner so we don't even have to do the store).
1314  */
1315 void optimizeCatchBlocks(const BlockList& blocks,
1316                          DceState& state,
1317                          IRUnit& unit,
1318                          const UseCounts& uses) {
1319
1320   for (auto block : blocks) {
1321     if (block->back().is(EndCatch) &&
1322         block->back().extra<EndCatch>()->mode !=
1323           EndCatchData::CatchMode::SideExit &&
1324         block->front().is(BeginCatch)) {
1325       auto const astk = AStack {
1326         block->back().src(1), block->back().extra<EndCatch>()->offset, 0
1327       };
1328       processCatchBlock(unit, state, block, astk.offset, uses);
1329     }
1330   }
1331 }
1332
1333 ////////////////////////////////////////////////////////////////////////////////
1334
1335 void killInstrAdjustRC(
1336   DceState& state,
1337   IRUnit& unit,
1338   IRInstruction* inst,
1339   jit::vector<IRInstruction*>& decs
1340 ) {
1341   auto anyRemaining = false;
1342   if (inst->consumesReferences()) {
1343     // ConsumesReference inputs that are definitely not moved can
1344     // simply be decreffed as a replacement for the dead consumesref
1345     // instruction
1346     auto srcIx = 0;
1347     for (auto src : inst->srcs()) {
1348       auto const ix = srcIx++;
1349       if (inst->consumesReference(ix) && src->type().maybe(TCounted)) {
1350         if (inst->mayMoveReference(ix)) {
1351           anyRemaining = true;
1352           continue;
1353         }
1354         auto const blk = inst->block();
1355         auto const ins = unit.gen(DecRef, inst->bcctx(), DecRefData{}, src);
1356         blk->insert(blk->iteratorTo(inst), ins);
1357         FTRACE(3, "Inserting {} to replace {}\n",
1358                ins->toString(), inst->toString());
1359         state[ins].setLive();
1360       }
1361     }
1362   }
1363   for (auto dec : decs) {
1364     auto replaced = dec->src(0) != inst->dst();
1365     auto srcIx = 0;
1366     if (anyRemaining) {
1367       // The remaining inputs might be moved, so may need to survive
1368       // until this instruction is decreffed
1369       for (auto src : inst->srcs()) {
1370         if (inst->mayMoveReference(srcIx++) && src->type().maybe(TCounted)) {
1371           if (!replaced) {
1372             FTRACE(3, "Converting {} to ", dec->toString());
1373             dec->setSrc(0, src);
1374             FTRACE(3, "{} for {}\n", dec->toString(), inst->toString());
1375             replaced = true;
1376             state[dec].setLive();
1377           } else {
1378             auto const blk = dec->block();
1379             auto const ins = unit.gen(DecRef, dec->bcctx(), DecRefData{}, src);
1380             blk->insert(blk->iteratorTo(dec), ins);
1381             FTRACE(3, "Inserting {} before {} for {}\n",
1382                    ins->toString(), dec->toString(), inst->toString());
1383             state[ins].setLive();
1384           }
1385         }
1386       }
1387     }
1388     if (!replaced) {
1389       FTRACE(3, "Killing {} for {}\n", dec->toString(), inst->toString());
1390       state[dec].setDead();
1391     }
1392   }
1393   state[inst].setDead();
1394 }
1395
1396 struct TrackedInstr {
1397   // DecRefs which refer to the tracked instruction.
1398   jit::vector<IRInstruction*> decs;
1399
1400   // Auxiliary instructions which must be killed if the tracked instruction is
1401   // killed.
1402   jit::vector<IRInstruction*> aux;
1403 };
1404
1405 //////////////////////////////////////////////////////////////////////
1406
1407 } // anonymous namespace
1408
1409 IRInstruction* resolveFpDefLabel(const SSATmp* fp) {
1410   IdSet<SSATmp> visited;
1411   auto const fpInst = resolveFpDefLabelImpl(fp, visited);
1412   assertx(fpInst);
1413   return fpInst;
1414 }
1415
1416 void convertToStackInst(IRUnit& unit, IRInstruction& inst) {
1417   assertx(inst.is(CheckLoc, AssertLoc, LdLoc, StLoc, LdLocAddr,
1418                   MemoGetStaticCache, MemoSetStaticCache,
1419                   MemoGetLSBCache, MemoSetLSBCache,
1420                   MemoGetInstanceCache, MemoSetInstanceCache));
1421   assertx(inst.src(0)->inst()->is(DefInlineFP));
1422
1423   auto const mainSP = unit.mainSP();
1424
1425   switch (inst.op()) {
1426     case StLoc:
1427       unit.replace(
1428         &inst,
1429         StStk,
1430         IRSPRelOffsetData { locToStkOff(*inst.extra<LocalId>(), inst.src(0)) },
1431         mainSP,
1432         inst.src(1)
1433       );
1434       return;
1435     case LdLoc:
1436       unit.replace(
1437         &inst,
1438         LdStk,
1439         IRSPRelOffsetData { locToStkOff(*inst.extra<LocalId>(), inst.src(0)) },
1440         inst.typeParam(),
1441         mainSP
1442       );
1443       return;
1444     case LdLocAddr:
1445       unit.replace(
1446         &inst,
1447         LdStkAddr,
1448         IRSPRelOffsetData { locToStkOff(*inst.extra<LocalId>(), inst.src(0)) },
1449         mainSP
1450       );
1451       retypeDests(&inst, &unit);
1452       return;
1453     case AssertLoc:
1454       unit.replace(
1455         &inst,
1456         AssertStk,
1457         IRSPRelOffsetData { locToStkOff(*inst.extra<LocalId>(), inst.src(0)) },
1458         inst.typeParam(),
1459         mainSP
1460       );
1461       return;
1462     case CheckLoc: {
1463       auto next = inst.next();
1464       unit.replace(
1465         &inst,
1466         CheckStk,
1467         IRSPRelOffsetData { locToStkOff(*inst.extra<LocalId>(), inst.src(0)) },
1468         inst.typeParam(),
1469         inst.taken(),
1470         mainSP
1471       );
1472       inst.setNext(next);
1473       return;
1474     }
1475     case MemoGetStaticCache:
1476     case MemoSetStaticCache:
1477     case MemoGetLSBCache:
1478     case MemoSetLSBCache: {
1479       auto& extra = *inst.extra<MemoCacheStaticData>();
1480       extra.stackOffset = locToStkOff(LocalId{extra.keys.first}, inst.src(0));
1481       inst.setSrc(0, mainSP);
1482       return;
1483     }
1484     case MemoGetInstanceCache:
1485     case MemoSetInstanceCache: {
1486       auto& extra = *inst.extra<MemoCacheInstanceData>();
1487       extra.stackOffset = locToStkOff(LocalId{extra.keys.first}, inst.src(0));
1488       inst.setSrc(0, mainSP);
1489       return;
1490     }
1491     default: break;
1492   }
1493   not_reached();
1494 }
1495
1496 void convertToInlineReturnNoFrame(IRUnit& unit, IRInstruction& inst) {
1497   assertx(inst.is(InlineReturn));
1498   auto const frameInst = inst.src(0)->inst();
1499   auto const spInst = frameInst->src(0)->inst();
1500   assertx(spInst->is(DefFrameRelSP, DefRegSP));
1501
1502   auto const calleeAROff = frameInst->extra<DefInlineFP>()->spOffset;
1503   auto const spOff = spInst->extra<FPInvOffsetData>()->offset;
1504
1505   auto const data = FPRelOffsetData {
1506     // Offset of the callee's return value relative to the frame pointer.
1507     calleeAROff.to<FPRelOffset>(spOff) + (kArRetOff / sizeof(TypedValue))
1508   };
1509   unit.replace(&inst, InlineReturnNoFrame, data);
1510 }
1511
1512 void mandatoryDCE(IRUnit& unit) {
1513   if (removeUnreachable(unit)) {
1514     // Removing unreachable incoming edges can change types, so if we changed
1515     // anything we have to reflow to maintain that IR invariant.
1516     reflowTypes(unit);
1517   }
1518   assertx(checkEverything(unit));
1519 }
1520
1521 void fullDCE(IRUnit& unit) {
1522   if (!RuntimeOption::EvalHHIRDeadCodeElim) {
1523     // This portion of DCE cannot be turned off, because it restores IR
1524     // invariants, and callers of fullDCE are allowed to rely on it for that.
1525     return mandatoryDCE(unit);
1526   }
1527
1528   Timer dceTimer(Timer::optimize_dce);
1529
1530   // kill unreachable code and remove any traces that are now empty
1531   auto const blocks = prepareBlocks(unit);
1532
1533   // At this point, all IR invariants must hold, because we've restored the
1534   // only one allowed to be violated before fullDCE in prepareBlocks.
1535   assertx(checkEverything(unit));
1536
1537   // mark the essential instructions and add them to the initial
1538   // work list; this will also mark reachable exit traces. All
1539   // other instructions marked dead.
1540   DceState state(unit, DceFlags());
1541   WorkList wl = initInstructions(unit, blocks, state);
1542
1543   UseCounts uses(unit, 0);
1544   jit::fast_map<IRInstruction*, TrackedInstr> rcInsts;
1545
1546   // process the worklist
1547   while (!wl.empty()) {
1548     auto* inst = wl.back();
1549     wl.pop_back();
1550     for (uint32_t ix = 0; ix < inst->numSrcs(); ++ix) {
1551       auto const src = inst->src(ix);
1552       IRInstruction* srcInst = src->inst();
1553       if (srcInst->op() == DefConst) continue;
1554
1555       if (RuntimeOption::EvalHHIRInlineFrameOpts) {
1556         if (srcInst->is(DefInlineFP)) {
1557           FTRACE(3, "adding use to {} from {}\n", *src, *inst);
1558           ++uses[src];
1559         }
1560       }
1561
1562       if (srcInst->producesReference() && canDCE(srcInst)) {
1563         ++uses[src];
1564         if (inst->is(DecRef)) {
1565           rcInsts[srcInst].decs.emplace_back(inst);
1566         }
1567         if (inst->is(InitPackedLayoutArray, StClosureArg)) {
1568           if (ix == 0) rcInsts[srcInst].aux.emplace_back(inst);
1569         }
1570       }
1571
1572       if (state[srcInst].isDead()) {
1573         state[srcInst].setLive();
1574         wl.push_back(srcInst);
1575       }
1576     }
1577   }
1578
1579   // If every use of a dce-able PRc instruction is a DecRef or PureStore based
1580   // on its dst, then we can kill it, and DecRef any of its consumesReference
1581   // inputs.
1582   for (auto& pair : rcInsts) {
1583     auto& info = pair.second;
1584     if (uses[pair.first->dst()] != info.decs.size() + info.aux.size()) continue;
1585     killInstrAdjustRC(state, unit, pair.first, info.decs);
1586     for (auto inst : info.aux) killInstrAdjustRC(state, unit, inst, info.decs);
1587   }
1588
1589   optimizeCatchBlocks(blocks, state, unit, uses);
1590
1591   if (RuntimeOption::EvalHHIRInlineFrameOpts) {
1592     optimizeActRecs(blocks, state, unit, uses);
1593   }
1594
1595   // Now remove instructions whose state is DEAD.
1596   removeDeadInstructions(unit, state);
1597 }
1598
1599 }}