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::jit {
  43
  44 TRACE_SET_MOD(hhir_dce);
  45
  46 bool canDCE(const IRInstruction& inst) {
  47   switch (inst.op()) {
  48   case AssertNonNull:
  49   case AssertType:
  50   case AbsDbl:
  51   case AddInt:
  52   case SubInt:
  53   case MulInt:
  54   case AndInt:
  55   case AddDbl:
  56   case SubDbl:
  57   case MulDbl:
  58   case Sqrt:
  59   case OrInt:
  60   case XorInt:
  61   case Shl:
  62   case Shr:
  63   case Lshr:
  64   case Floor:
  65   case Ceil:
  66   case XorBool:
  67   case Mod:
  68   case ConvDblToBool:
  69   case ConvIntToBool:
  70   case ConvStrToBool:
  71   case ConvBoolToDbl:
  72   case ConvIntToDbl:
  73   case ConvStrToDbl:
  74   case ConvResToDbl:
  75   case ConvBoolToInt:
  76   case ConvDblToInt:
  77   case ConvStrToInt:
  78   case ConvResToInt:
  79   case ConvDblToStr:
  80   case ConvIntToStr:
  81   case DblAsBits:
  82   case ConvPtrToLval:
  83   case NewColFromArray:
  84   case GtInt:
  85   case GteInt:
  86   case LtInt:
  87   case LteInt:
  88   case EqInt:
  89   case NeqInt:
  90   case CmpInt:
  91   case GtDbl:
  92   case GteDbl:
  93   case LtDbl:
  94   case LteDbl:
  95   case EqDbl:
  96   case NeqDbl:
  97   case CmpDbl:
  98   case GtStr:
  99   case GteStr:
 100   case LtStr:
 101   case LteStr:
 102   case SameStr:
 103   case NSameStr:
 104   case CmpStr:
 105   case GtBool:
 106   case GteBool:
 107   case LtBool:
 108   case LteBool:
 109   case EqBool:
 110   case NeqBool:
 111   case CmpBool:
 112   case SameObj:
 113   case NSameObj:
 114   case EqRes:
 115   case NeqRes:
 116   case EqCls:
 117   case EqLazyCls:
 118   case EqFunc:
 119   case EqStrPtr:
 120   case EqArrayDataPtr:
 121   case FuncHasReifiedGenerics:
 122   case ClassHasReifiedGenerics:
 123   case HasReifiedParent:
 124   case InstanceOf:
 125   case InstanceOfIface:
 126   case InstanceOfIfaceVtable:
 127   case ExtendsClass:
 128   case InstanceOfBitmask:
 129   case NInstanceOfBitmask:
 130   case InterfaceSupportsArrLike:
 131   case InterfaceSupportsStr:
 132   case InterfaceSupportsInt:
 133   case InterfaceSupportsDbl:
 134   case HasToString:
 135   case IsType:
 136   case IsNType:
 137   case IsTypeMem:
 138   case IsNTypeMem:
 139   case IsLegacyArrLike:
 140   case IsWaitHandle:
 141   case IsCol:
 142   case LdStk:
 143   case LdLoc:
 144   case LdLocForeign:
 145   case LdStkAddr:
 146   case LdLocAddr:
 147   case LdRDSAddr:
 148   case LdMem:
 149   case LdContField:
 150   case LdClsInitElem:
 151   case LdIterBase:
 152   case LdIterPos:
 153   case LdIterEnd:
 154   case LdFrameThis:
 155   case LdFrameCls:
 156   case LdSmashable:
 157   case LdSmashableFunc:
 158   case LdClsFromClsMeth:
 159   case LdFuncFromClsMeth:
 160   case LdClsFromRClsMeth:
 161   case LdFuncFromRClsMeth:
 162   case LdGenericsFromRClsMeth:
 163   case LdFuncFromRFunc:
 164   case LdGenericsFromRFunc:
 165   case LdTVFromRDS:
 166   case ConvFuncPrologueFlagsToARFlags:
 167   case DefConst:
 168   case DefFuncPrologueCallee:
 169   case DefFuncPrologueCtx:
 170   case DefFuncPrologueFlags:
 171   case DefFuncPrologueNumArgs:
 172   case Conjure:
 173   case LdClsInitData:
 174   case LookupClsRDS:
 175   case LdClsMethodCacheCls:
 176   case LdFuncVecLen:
 177   case LdClsMethod:
 178   case LdSubClsCns:
 179   case LdIfaceMethod:
 180   case LdPropAddr:
 181   case LdObjClass:
 182   case LdClsName:
 183   case LdLazyClsName:
 184   case LdLazyCls:
 185   case LdFuncCls:
 186   case LdFuncInOutBits:
 187   case LdFuncNumParams:
 188   case LdFuncName:
 189   case LdMethCallerName:
 190   case LdStrLen:
 191   case LdMonotypeDictTombstones:
 192   case LdMonotypeDictKey:
 193   case LdMonotypeDictVal:
 194   case LdMonotypeVecElem:
 195   case LdVecElem:
 196   case LdVecElemAddr:
 197   case NewInstanceRaw:
 198   case NewLoggingArray:
 199   case NewDictArray:
 200   case NewCol:
 201   case NewPair:
 202   case NewRFunc:
 203   case NewRClsMeth:
 204   case LdRetVal:
 205   case Mov:
 206   case CountVec:
 207   case CountDict:
 208   case CountKeyset:
 209   case CountCollection:
 210   case Nop:
 211   case AKExistsDict:
 212   case AKExistsKeyset:
 213   case LdBindAddr:
 214   case LdSSwitchDest:
 215   case LdClosureCls:
 216   case LdClosureThis:
 217   case CreateSSWH:
 218   case LdContActRec:
 219   case LdContArValue:
 220   case LdContArKey:
 221   case LdWHState:
 222   case LdWHResult:
 223   case LdWHNotDone:
 224   case LdAFWHActRec:
 225   case LdMIStateTempBaseAddr:
 226   case StringIsset:
 227   case ColIsEmpty:
 228   case ColIsNEmpty:
 229   case LdUnwinderValue:
 230   case LdColVec:
 231   case LdColDict:
 232   case OrdStr:
 233   case ChrInt:
 234   case CheckRange:
 235   case LdMBase:
 236   case MethodExists:
 237   case LdTVAux:
 238   case DictGetQuiet:
 239   case DictGetK:
 240   case DictIsset:
 241   case DictIdx:
 242   case KeysetGetQuiet:
 243   case KeysetGetK:
 244   case KeysetIsset:
 245   case KeysetIdx:
 246   case VecFirst:
 247   case VecLast:
 248   case DictFirst:
 249   case DictFirstKey:
 250   case DictLast:
 251   case DictLastKey:
 252   case KeysetFirst:
 253   case KeysetLast:
 254   case GetTime:
 255   case GetTimeNs:
 256   case Select:
 257   case LdARFlags:
 258   case FuncHasAttr:
 259   case ClassHasAttr:
 260   case IsFunReifiedGenericsMatched:
 261   case LdFuncRequiredCoeffects:
 262   case LdARFunc:
 263   case StrictlyIntegerConv:
 264   case GetMemoKeyScalar:
 265   case LookupSPropSlot:
 266   case ConstructClosure:
 267   case AllocBespokeStructDict:
 268   case AllocStructDict:
 269   case AllocVec:
 270   case GetDictPtrIter:
 271   case GetVecPtrIter:
 272   case AdvanceDictPtrIter:
 273   case AdvanceVecPtrIter:
 274   case LdPtrIterKey:
 275   case LdPtrIterVal:
 276   case EqPtrIter:
 277   case LdUnitPerRequestFilepath:
 278   case DirFromFilepath:
 279   case BespokeGet:
 280   case BespokeIterFirstPos:
 281   case BespokeIterLastPos:
 282   case BespokeIterEnd:
 283   case BespokeIterGetKey:
 284   case BespokeIterGetVal:
 285   case LoadBCSP:
 286   case LdResolvedTypeCnsNoCheck:
 287   case LdResolvedTypeCnsClsName:
 288   case LdClsCtxCns:
 289   case AllocInitROM:
 290   case VoidPtrAsDataType:
 291   case CopyArray:
 292   case StructDictElemAddr:
 293   case StructDictSlotInPos:
 294   case LdStructDictKey:
 295   case LdStructDictVal:
 296   case LdImplicitContext:
 297   case CallViolatesModuleBoundary:
 298     assertx(!inst.isControlFlow());
 299     return true;
 300
 301   // These may raise oom, but its still ok to delete them if the
 302   // result is unused
 303   case ConcatIntStr:
 304   case ConcatStrInt:
 305   case ConcatStrStr:
 306   case ConcatStr3:
 307   case ConcatStr4:
 308   case AddNewElemKeyset:
 309   case AddNewElemVec:
 310     return true;
 311
 312   // Some of these conversion functions can run arbitrary PHP code.
 313   case ConvObjToDbl:
 314   case ConvTVToDbl:
 315   case ConvObjToInt:
 316   case ConvTVToInt:
 317   case ConvTVToBool:
 318   case ConvObjToBool:
 319   case ConvObjToStr:
 320   case ConvTVToStr:
 321   case ConvArrLikeToVec:
 322   case ConvObjToVec:
 323   case ConvArrLikeToDict:
 324   case ConvObjToDict:
 325   case ConvArrLikeToKeyset:
 326   case ConvObjToKeyset:
 327   case LdOutAddr:
 328     return !opcodeMayRaise(inst.op()) &&
 329       (!inst.consumesReferences() || inst.producesReference());
 330
 331   case DbgTraceCall:
 332   case AKExistsObj:
 333   case StStk:
 334   case StStkMeta:
 335   case StStkRange:
 336   case StOutValue:
 337   case CheckIter:
 338   case CheckType:
 339   case CheckNullptr:
 340   case CheckTypeMem:
 341   case CheckDictKeys:
 342   case CheckSmashableClass:
 343   case CheckLoc:
 344   case CheckStk:
 345   case CheckMBase:
 346   case AssertLoc:
 347   case AssertStk:
 348   case AssertMBase:
 349   case CheckInit:
 350   case CheckInitMem:
 351   case CheckCold:
 352   case EndGuards:
 353   case CheckNonNull:
 354   case DivDbl:
 355   case DivInt:
 356   case AddIntO:
 357   case AddOffset:
 358   case SubIntO:
 359   case MulIntO:
 360
 361   case GtObj:
 362   case GteObj:
 363   case LtObj:
 364   case LteObj:
 365   case EqObj:
 366   case NeqObj:
 367   case CmpObj:
 368   case CmpRes:
 369   case GtRes:
 370   case GteRes:
 371   case LtRes:
 372   case LteRes:
 373   case GtArrLike:
 374   case GteArrLike:
 375   case LtArrLike:
 376   case LteArrLike:
 377   case CmpArrLike:
 378   case JmpZero:
 379   case JmpNZero:
 380   case JmpSSwitchDest:
 381   case JmpSwitchDest:
 382   case ProfileSwitchDest:
 383   case CheckSurpriseFlags:
 384   case CheckSurpriseAndStack:
 385   case HandleRequestSurprise:
 386   case ReturnHook:
 387   case SuspendHookAwaitEF:
 388   case SuspendHookAwaitEG:
 389   case SuspendHookAwaitR:
 390   case SuspendHookCreateCont:
 391   case SuspendHookYield:
 392   case EndBlock:
 393   case Unreachable:
 394   case Jmp:
 395   case DefLabel:
 396   case LdPairElem:
 397   case LdClsCtor:
 398   case LdCls:
 399   case LdClsCached:
 400   case LdClsCachedSafe:
 401   case LdCns:
 402   case LdTypeCns:
 403   case LdTypeCnsNoThrow:
 404   case LdTypeCnsClsName:
 405   case IsTypeStructCached:
 406   case LookupCnsE:
 407   case LdClsCns:
 408   case InitClsCns:
 409   case InitSubClsCns:
 410   case LdResolvedTypeCns:
 411   case CheckSubClsCns:
 412   case LdClsCnsVecLen:
 413   case LookupClsMethodFCache:
 414   case LookupClsMethodCache:
 415   case LookupClsMethod:
 416   case LdGblAddr:
 417   case LdGblAddrDef:
 418   case LdClsPropAddrOrNull:
 419   case LdClsPropAddrOrRaise:
 420   case LdInitRDSAddr:
 421   case LdInitPropAddr:
 422   case LdObjMethodD:
 423   case LdObjMethodS:
 424   case LdObjInvoke:
 425   case LdFunc:
 426   case LdFuncCached:
 427   case LookupFuncCached:
 428   case AllocObj:
 429   case AllocObjReified:
 430   case NewClsMeth:
 431   case FuncCred:
 432   case InitProps:
 433   case PropTypeRedefineCheck:
 434   case InitSProps:
 435   case InitObjProps:
 436   case InitObjMemoSlots:
 437   case LockObj:
 438   case DebugBacktrace:
 439   case InitThrowableFileAndLine:
 440   case ConstructInstance:
 441   case InitDictElem:
 442   case InitStructElem:
 443   case InitStructPositions:
 444   case InitVecElem:
 445   case InitVecElemLoop:
 446   case NewKeysetArray:
 447   case NewStructDict:
 448   case NewBespokeStructDict:
 449   case Clone:
 450   case InlineCall:
 451   case Call:
 452   case CallFuncEntry:
 453   case NativeImpl:
 454   case CallBuiltin:
 455   case RetCtrl:
 456   case AsyncFuncRet:
 457   case AsyncFuncRetPrefetch:
 458   case AsyncFuncRetSlow:
 459   case AsyncGenRetR:
 460   case AsyncGenYieldR:
 461   case AsyncSwitchFast:
 462   case GenericRetDecRefs:
 463   case StClsInitElem:
 464   case StImplicitContext:
 465   case StImplicitContextWH:
 466   case StMem:
 467   case StMemMeta:
 468   case StIterBase:
 469   case StIterType:
 470   case StIterEnd:
 471   case StIterPos:
 472   case StLoc:
 473   case StLocMeta:
 474   case StLocRange:
 475   case StPtrAt:
 476   case StVMFP:
 477   case StVMSP:
 478   case StVMPC:
 479   case StVMReturnAddr:
 480   case StVMRegState:
 481   case StTVInRDS:
 482   case StTypeAt:
 483   case ReqBindJmp:
 484   case ReqInterpBBNoTranslate:
 485   case ReqRetranslate:
 486   case ReqRetranslateOpt:
 487   case IncRef:
 488   case DecRef:
 489   case DecRefNZ:
 490   case ProfileDecRef:
 491   case ReleaseShallow:
 492   case DecReleaseCheck:
 493   case DefFP:
 494   case DefFuncEntryFP:
 495   case DefFrameRelSP:
 496   case DefRegSP:
 497   case InitFrame:
 498   case Count:
 499   case VerifyParam:
 500   case VerifyParamCallable:
 501   case VerifyParamCls:
 502   case VerifyParamCoerce:
 503   case VerifyParamFail:
 504   case VerifyParamFailHard:
 505   case VerifyReifiedLocalType:
 506   case VerifyReifiedReturnType:
 507   case VerifyRet:
 508   case VerifyRetCallable:
 509   case VerifyRetCls:
 510   case VerifyRetCoerce:
 511   case VerifyRetFail:
 512   case VerifyRetFailHard:
 513   case VerifyProp:
 514   case VerifyPropAll:
 515   case VerifyPropCls:
 516   case VerifyPropCoerce:
 517   case VerifyPropCoerceAll:
 518   case VerifyPropFail:
 519   case VerifyPropFailHard:
 520   case ThrowUninitLoc:
 521   case ThrowUndefPropException:
 522   case RaiseTooManyArg:
 523   case RaiseError:
 524   case RaiseErrorOnInvalidIsAsExpressionType:
 525   case RaiseWarning:
 526   case RaiseNotice:
 527   case ThrowArrayIndexException:
 528   case ThrowArrayKeyException:
 529   case RaiseForbiddenDynCall:
 530   case RaiseForbiddenDynConstruct:
 531   case RaiseCoeffectsCallViolation:
 532   case RaiseCoeffectsFunParamTypeViolation:
 533   case RaiseCoeffectsFunParamCoeffectRulesViolation:
 534   case RaiseStrToClassNotice:
 535   case RaiseModuleBoundaryViolation:
 536   case RaiseImplicitContextStateInvalid:
 537   case CheckClsMethFunc:
 538   case CheckClsReifiedGenericMismatch:
 539   case CheckClsRGSoft:
 540   case CheckFunReifiedGenericMismatch:
 541   case CheckInOutMismatch:
 542   case CheckReadonlyMismatch:
 543   case PrintStr:
 544   case PrintInt:
 545   case PrintBool:
 546   case GetMemoKey:
 547   case InterpOne:
 548   case InterpOneCF:
 549   case OODeclExists:
 550   case StClosureArg:
 551   case CreateGen:
 552   case CreateAGen:
 553   case CreateAAWH:
 554   case CreateAFWH:
 555   case CreateAGWH:
 556   case AFWHPrepareChild:
 557   case StArResumeAddr:
 558   case ContEnter:
 559   case ContCheckNext:
 560   case ContValid:
 561   case ContArIncKey:
 562   case ContArIncIdx:
 563   case ContArUpdateIdx:
 564   case LdContResumeAddr:
 565   case StContArState:
 566   case StContArValue:
 567   case StContArKey:
 568   case AFWHBlockOn:
 569   case AFWHPushTailFrame:
 570   case CountWHNotDone:
 571   case IncStat:
 572   case IncProfCounter:
 573   case IncCallCounter:
 574   case DbgAssertRefCount:
 575   case DbgAssertFunc:
 576   case DbgCheckLocalsDecRefd:
 577   case RBTraceEntry:
 578   case RBTraceMsg:
 579   case ZeroErrorLevel:
 580   case RestoreErrorLevel:
 581   case IterInit:
 582   case IterInitK:
 583   case LIterInit:
 584   case LIterInitK:
 585   case IterNext:
 586   case IterNextK:
 587   case LIterNext:
 588   case LIterNextK:
 589   case IterFree:
 590   case KillActRec:
 591   case KillIter:
 592   case KillLoc:
 593   case BaseG:
 594   case PropX:
 595   case PropQ:
 596   case PropDX:
 597   case CGetProp:
 598   case CGetPropQ:
 599   case SetProp:
 600   case UnsetProp:
 601   case SetOpProp:
 602   case IncDecProp:
 603   case IssetProp:
 604   case ElemX:
 605   case CheckMissingKeyInArrLike:
 606   case CheckArrayCOW:
 607   case ProfileDictAccess:
 608   case CheckDictOffset:
 609   case ProfileKeysetAccess:
 610   case CheckKeysetOffset:
 611   case ProfileArrayCOW:
 612   case ElemDictD:
 613   case ElemDictU:
 614   case ElemDictK:
 615   case ElemDX:
 616   case ElemUX:
 617   case DictGet:
 618   case KeysetGet:
 619   case StringGet:
 620   case OrdStrIdx:
 621   case MapGet:
 622   case CGetElem:
 623   case DictSet:
 624   case MapSet:
 625   case VectorSet:
 626   case BespokeSet:
 627   case BespokeUnset:
 628   case StructDictUnset:
 629   case BespokeAppend:
 630   case SetElem:
 631   case SetRange:
 632   case SetRangeRev:
 633   case UnsetElem:
 634   case SetOpElem:
 635   case IncDecElem:
 636   case SetNewElem:
 637   case SetNewElemDict:
 638   case SetNewElemVec:
 639   case SetNewElemKeyset:
 640   case ReserveVecNewElem:
 641   case VectorIsset:
 642   case PairIsset:
 643   case MapIsset:
 644   case IssetElem:
 645   case ProfileType:
 646   case ProfileCall:
 647   case ProfileMethod:
 648   case ProfileSubClsCns:
 649   case ProfileGlobal:
 650   case ProfileCoeffectFunParam:
 651   case CheckVecBounds:
 652   case BespokeElem:
 653   case BespokeEscalateToVanilla:
 654   case BespokeGetThrow:
 655   case LdTypeStructureVal:
 656   case LdTypeStructureValCns:
 657   case LdVectorSize:
 658   case BeginCatch:
 659   case EndCatch:
 660   case EnterTCUnwind:
 661   case UnwindCheckSideExit:
 662   case DbgTrashStk:
 663   case DbgTrashFrame:
 664   case DbgTrashMem:
 665   case EnterPrologue:
 666   case ExitPrologue:
 667   case EnterTranslation:
 668   case CheckStackOverflow:
 669   case CheckSurpriseFlagsEnter:
 670   case JmpPlaceholder:
 671   case ThrowOutOfBounds:
 672   case ThrowInvalidArrayKey:
 673   case ThrowInvalidOperation:
 674   case ThrowCallReifiedFunctionWithoutGenerics:
 675   case ThrowDivisionByZeroException:
 676   case ThrowHasThisNeedStatic:
 677   case ThrowLateInitPropError:
 678   case ThrowMissingArg:
 679   case ThrowMissingThis:
 680   case ThrowParameterWrongType:
 681   case ThrowInOutMismatch:
 682   case ThrowReadonlyMismatch:
 683   case ThrowCannotModifyReadonlyCollection:
 684   case ThrowLocalMustBeValueTypeException:
 685   case ThrowMustBeEnclosedInReadonly:
 686   case ThrowMustBeMutableException:
 687   case ThrowMustBeReadonlyException:
 688   case ThrowMustBeValueTypeException:
 689   case StMBase:
 690   case StMROProp:
 691   case CheckMROProp:
 692   case FinishMemberOp:
 693   case BeginInlining:
 694   case EndInlining:
 695   case SetOpTV:
 696   case OutlineSetOp:
 697   case ConjureUse:
 698   case LdClsMethodFCacheFunc:
 699   case LdClsMethodCacheFunc:
 700   case LogArrayReach:
 701   case LogGuardFailure:
 702   case ProfileInstanceCheck:
 703   case MemoGetStaticValue:
 704   case MemoGetStaticCache:
 705   case MemoGetLSBValue:
 706   case MemoGetLSBCache:
 707   case MemoGetInstanceValue:
 708   case MemoGetInstanceCache:
 709   case MemoSetStaticValue:
 710   case MemoSetStaticCache:
 711   case MemoSetLSBValue:
 712   case MemoSetLSBCache:
 713   case MemoSetInstanceValue:
 714   case MemoSetInstanceCache:
 715   case ThrowAsTypeStructException:
 716   case RecordReifiedGenericsAndGetTSList:
 717   case ResolveTypeStruct:
 718   case CheckRDSInitialized:
 719   case MarkRDSInitialized:
 720   case MarkRDSAccess:
 721   case ProfileProp:
 722   case ProfileIsTypeStruct:
 723   case StFrameCtx:
 724   case StFrameFunc:
 725   case StFrameMeta:
 726   case LookupClsCns:
 727   case LookupClsCtxCns:
 728   case ArrayMarkLegacyShallow:
 729   case ArrayMarkLegacyRecursive:
 730   case ArrayUnmarkLegacyShallow:
 731   case ArrayUnmarkLegacyRecursive:
 732   case ProfileArrLikeProps:
 733   case CheckFuncNeedsCoverage:
 734   case RecordFuncCall:
 735   case StructDictSlot:
 736   case StructDictAddNextSlot:
 737   case StructDictTypeBoundCheck:
 738   case LdCoeffectFunParamNaive:
 739   case DeserializeLazyProp:
 740   case GetClsRGProp:
 741     return false;
 742
 743   case IsTypeStruct:
 744   case EqStr:
 745   case NeqStr:
 746     return !opcodeMayRaise(inst.op());
 747
 748   case EqArrLike:
 749   case NeqArrLike:
 750   case SameArrLike:
 751   case NSameArrLike:
 752     return !inst.mayRaiseErrorWithSources();
 753   }
 754   not_reached();
 755 }
 756
 757 namespace {
 758
 759 /* DceFlags tracks the state of one instruction during dead code analysis. */
 760 struct DceFlags {
 761   DceFlags()
 762     : m_state(DEAD)
 763   {}
 764
 765   bool isDead() const { return m_state == DEAD; }
 766   void setDead()      { m_state = DEAD; }
 767   void setLive()      { m_state = LIVE; }
 768
 769   std::string toString() const {
 770     std::array<const char*,2> const names = {{
 771       "DEAD",
 772       "LIVE",
 773     }};
 774     return folly::format(
 775       "{}",
 776       m_state < names.size() ? names[m_state] : "<invalid>"
 777     ).str();
 778   }
 779
 780 private:
 781   enum {
 782     DEAD = 0,
 783     LIVE,
 784   };
 785   uint8_t m_state:1;
 786 };
 787 static_assert(sizeof(DceFlags) == 1, "sizeof(DceFlags) should be 1 byte");
 788
 789 // DCE state indexed by instr->id().
 790 using DceState = StateVector<IRInstruction, DceFlags>;
 791 using UseCounts = StateVector<SSATmp, uint32_t>;
 792 // Set of live DefLabel operands (keyed by DefLabel and index)
 793 using DefLabelLiveness = jit::fast_set<std::pair<IRInstruction*, size_t>>;
 794 // Worklist is instruction to process. If the instruction is a
 795 // DefLabel, the second item is the index of the operand (DefLabel is
 796 // treated separately for each operand).
 797 using WorkList = jit::vector<std::pair<IRInstruction*, size_t>>;
 798
 799 void removeDeadInstructions(IRUnit& unit,
 800                             const DceState& state,
 801                             const DefLabelLiveness& defLabelLive) {
 802   postorderWalk(
 803     unit,
 804     [&](Block* block) {
 805       auto const next = block->next();
 806       auto const bcctx = block->back().bcctx();
 807       block->remove_if(
 808         [&] (const IRInstruction& inst) {
 809           // Don't attempt to remove a Jmp feeding a DefLabel. It will
 810           // be dealt with below.
 811           if (inst.is(Jmp) && inst.numSrcs() > 0) return false;
 812
 813           // DecReleaseCheck will be dealt with below.
 814           if (inst.is(DecReleaseCheck)) return false;
 815
 816           ONTRACE(
 817             4,
 818             if (state[inst].isDead()) {
 819               FTRACE(1, "Removing dead instruction {}\n", inst.toString());
 820             }
 821           );
 822
 823           auto const dead = state[inst].isDead();
 824           assertx(!dead || !inst.taken() || inst.taken()->isCatch());
 825           return dead;
 826         }
 827       );
 828
 829       if (!block->empty()) {
 830         auto& front = block->front();
 831         if (front.is(DefLabel)) {
 832           // If the DefLabel was completely dead, it would have been
 833           // removed above.
 834           assertx(!state[&front].isDead());
 835           // Remove any dead individual operands
 836           auto dstIdx = 0;
 837           auto const numDsts = front.numDsts();
 838           for (auto i = 0; i < numDsts; ++i) {
 839             if (!defLabelLive.count(std::make_pair(&front, i))) {
 840               FTRACE(1, "Removing dead DefLabel dst {}: {}\n",
 841                      i, front.toString());
 842               front.deleteDst(dstIdx);
 843             } else {
 844               ++dstIdx;
 845             }
 846           }
 847           assertx(front.numDsts() > 0);
 848         }
 849
 850         auto& back = block->back();
 851         if (back.is(Jmp) && back.numSrcs() > 0) {
 852           if (state[&back].isDead()) {
 853             // If the Jmp's operands are completely dead, we can't
 854             // remove it (because it's control flow), but we can turn
 855             // it into a normal Jmp.
 856             FTRACE(1, "Removing dead instruction {}\n", back.toString());
 857             back.setSrcs(0, nullptr);
 858           } else {
 859             // Otherwise, similarily to the DefLabel, remove
 860             // individual dead operands.
 861             auto srcIdx = 0;
 862             auto const numSrcs = back.numSrcs();
 863             for (auto i = 0; i < numSrcs; ++i) {
 864               auto& defLabel = block->taken()->front();
 865               assertx(defLabel.is(DefLabel));
 866               if (!defLabelLive.count(std::make_pair(&defLabel, i))) {
 867                 FTRACE(1, "Removing dead Jmp src {}: {}\n",
 868                        i, back.toString());
 869                 back.deleteSrc(srcIdx);
 870               } else {
 871                 ++srcIdx;
 872               }
 873             }
 874           }
 875         }
 876
 877         if (back.is(DecReleaseCheck) && state[&back].isDead()) {
 878           block->erase(block->backIter());
 879           block->push_back(unit.gen(Jmp, bcctx, next));
 880         }
 881       }
 882
 883       if (block->empty() || !block->back().isBlockEnd()) {
 884         assertx(next);
 885         block->push_back(unit.gen(Jmp, bcctx, next));
 886       }
 887     }
 888   );
 889 }
 890
 891 // removeUnreachable erases unreachable blocks from unit, and returns
 892 // a sorted list of the remaining blocks.
 893 BlockList prepareBlocks(IRUnit& unit) {
 894   FTRACE(1, "RemoveUnreachable:vvvvvvvvvvvvvvvvvvvv\n");
 895   SCOPE_EXIT { FTRACE(1, "RemoveUnreachable:^^^^^^^^^^^^^^^^^^^^\n"); };
 896
 897   auto const blocks = rpoSortCfg(unit);
 898
 899   // 1. perform copy propagation on every instruction
 900   for (auto block : blocks) {
 901     for (auto& inst : *block) {
 902       copyProp(&inst);
 903     }
 904   }
 905
 906   // 2. erase unreachable blocks and get an rpo sorted list of what remains.
 907   bool needsReflow = removeUnreachable(unit);
 908
 909   // 3. if we removed any whole blocks that ended in Jmp instructions, reflow
 910   //    all types in case they change the incoming types of DefLabel
 911   //    instructions.
 912   if (needsReflow) reflowTypes(unit);
 913
 914   return blocks;
 915 }
 916
 917 WorkList initInstructions(const IRUnit& unit, const BlockList& blocks,
 918                           DceState& state) {
 919   TRACE(1, "DCE(initInstructions):vvvvvvvvvvvvvvvvvvvv\n");
 920   // Mark reachable, essential, instructions live and enqueue them.
 921   WorkList wl;
 922   wl.reserve(unit.numInsts());
 923   forEachInst(blocks, [&] (IRInstruction* inst) {
 924     // Instructions that cannot be removed are automatically live. The
 925     // exception is DefLabels and Jmps that feed a DefLabel. There
 926     // aren't normally DCEable, but will be dealt with specially.
 927     if (!canDCE(*inst) &&
 928         !inst->is(DefLabel) &&
 929         !(inst->is(Jmp) && inst->numSrcs() > 0)) {
 930       state[inst].setLive();
 931       wl.push_back(std::make_pair(inst, 0));
 932     }
 933   });
 934   TRACE(1, "DCE:^^^^^^^^^^^^^^^^^^^^\n");
 935   return wl;
 936 }
 937
 938 //////////////////////////////////////////////////////////////////////
 939
 940 struct TrackedInstr {
 941   // DecRefs which refer to the tracked instruction.
 942   jit::vector<IRInstruction*> decs;
 943
 944   // Auxiliary instructions which must be killed if the tracked instruction is
 945   // killed.
 946   jit::vector<IRInstruction*> aux;
 947
 948   // Stores to the stack in catch traces that can be killed to kill the
 949   // tracked instruction.
 950   jit::vector<IRInstruction*> stores;
 951 };
 952
 953 void processCatchBlock(IRUnit& unit, DceState& state, Block* block,
 954                        const UseCounts& uses,
 955                        jit::fast_map<IRInstruction*, TrackedInstr>& rcInsts) {
 956   assertx(block->front().is(BeginCatch));
 957   assertx(block->back().is(EndCatch));
 958
 959   auto constexpr numTrackedSlots = 64;
 960   auto constexpr wholeRange = std::make_pair(0, numTrackedSlots);
 961   auto const stackTop = block->back().extra<EndCatch>()->offset;
 962   auto const stackRange = [&] {
 963     // If the catch block occurs within an inlined frame the outer stack
 964     // locations (those above the inlined frame) are not dead and cannot be
 965     // elided as we may not throw through the outer callers.
 966     if (block->back().src(0)->inst()->is(BeginInlining)) {
 967       auto const extra = block->back().src(0)->inst()->extra<BeginInlining>();
 968       auto const spOff = extra->spOffset;
 969       assertx(stackTop <= spOff);
 970       if (spOff < stackTop + numTrackedSlots) {
 971         return AStack::range(stackTop, spOff);
 972       }
 973     }
 974     return AStack::range(stackTop, stackTop + numTrackedSlots);
 975   }();
 976
 977   // Nothing to optimize if the stack is empty
 978   if (stackRange.size() == 0) return;
 979
 980   std::bitset<numTrackedSlots> usedLocations = {};
 981   // stores that are only read by the EndCatch
 982   jit::fast_set<IRInstruction*> candidateStores;
 983   // Any IncRefs we see; if they correspond to stores above, we can
 984   // replace the store with a store of Null, and kill the IncRef.
 985   jit::fast_map<SSATmp*, std::vector<Block::iterator>> candidateIncRefs;
 986
 987   auto const range =
 988     [&] (const AliasClass& cls) -> std::pair<int, int> {
 989       if (!cls.maybe(stackRange)) return {};
 990       auto const stk = cls.stack();
 991       if (!stk) return wholeRange;
 992       auto const lowest_upper = std::min(stackRange.high, stk->high);
 993       auto const highest_lower = std::max(stackRange.low, stk->low);
 994       if (lowest_upper <= highest_lower) return {};
 995       return {
 996         highest_lower.offset - stackRange.low.offset,
 997         lowest_upper.offset - stackRange.low.offset
 998       };
 999     };
1000
1001   auto const process_stack =
1002     [&] (const AliasClass& cls) {
1003       auto r = range(cls);
1004       if (r == wholeRange) {
1005         usedLocations.set();
1006       } else {
1007         while (r.first < r.second) {
1008           usedLocations.set(r.first++);
1009         }
1010       }
1011       return false;
1012     };
1013
1014   auto const do_store =
1015     [&] (const AliasClass& cls, IRInstruction* store) {
1016       if (!store->is(StStk, StStkMeta)) return false;
1017       auto const stk = cls.is_stack();
1018       if (!stk) return process_stack(cls);
1019       auto const r = range(cls);
1020       if (r.first != r.second) {
1021         assertx(r.second == r.first + 1);
1022         if (!usedLocations.test(r.first)) {
1023           usedLocations.set(r.first);
1024           candidateStores.insert(store);
1025         }
1026       }
1027       return false;
1028     };
1029
1030   auto done = false;
1031   for (auto inst = block->end(); inst != block->begin(); ) {
1032     --inst;
1033     if (inst->is(EndCatch)) {
1034       continue;
1035     }
1036     if (inst->is(IncRef)) {
1037       candidateIncRefs[inst->src(0)].push_back(inst);
1038       continue;
1039     }
1040     if (done) continue;
1041     auto const effects = canonicalize(memory_effects(*inst));
1042     done = match<bool>(
1043       effects,
1044       [&] (IrrelevantEffects)    { return false; },
1045       [&] (UnknownEffects)       { return true; },
1046       [&] (ReturnEffects x)      { return true; },
1047       [&] (CallEffects x)        { return true; },
1048       [&] (GeneralEffects x)     {
1049         return
1050           process_stack(x.loads) ||
1051           process_stack(x.inout) ||
1052           process_stack(x.stores) ||
1053           process_stack(x.backtrace) ||
1054           process_stack(x.kills);
1055       },
1056       [&] (PureLoad x)           { return process_stack(x.src); },
1057       [&] (PureStore x)          { return do_store(x.dst, &*inst); },
1058       [&] (ExitEffects x)        { return process_stack(x.live); },
1059       [&] (PureInlineCall x) {
1060         return
1061           process_stack(x.base) ||
1062           process_stack(x.actrec);
1063       }
1064     );
1065   }
1066
1067   for (auto store : candidateStores) {
1068     auto const src = store->src(1);
1069     auto const it = candidateIncRefs.find(src);
1070     if (it != candidateIncRefs.end()) {
1071       FTRACE(3, "Erasing {} for {}\n",
1072              it->second.back()->toString(), store->toString());
1073       block->erase(it->second.back());
1074       if (it->second.size() > 1) {
1075         it->second.pop_back();
1076       } else {
1077         candidateIncRefs.erase(it);
1078       }
1079     } else if (src->type().maybe(TCounted)) {
1080       auto const srcInst = src->inst();
1081       if (!srcInst->producesReference() ||
1082           !canDCE(*srcInst) ||
1083           uses[src] != 1) {
1084         if (srcInst->producesReference() && canDCE(*srcInst)) {
1085           rcInsts[srcInst].stores.emplace_back(store);
1086         }
1087         continue;
1088       } else {
1089         FTRACE(3, "Erasing {} for {}\n",
1090                srcInst->toString(), store->toString());
1091         state[srcInst].setDead();
1092       }
1093     }
1094     store->setSrc(1, unit.cns(TInitNull));
1095   }
1096 }
1097
1098 /*
1099  * A store to the stack which is post-dominated by the EndCatch and
1100  * not otherwise read is only there to ensure the unwinder DecRefs the
1101  * value it contains. If there's also an IncRef of the value in the
1102  * catch trace we can just store InitNull to the stack location and
1103  * drop the IncRef (and later, maybe adjust the sp of the
1104  * catch-trace's owner so we don't even have to do the store).
1105  */
1106 void optimizeCatchBlocks(const BlockList& blocks,
1107                          DceState& state,
1108                          IRUnit& unit,
1109                          const UseCounts& uses,
1110                          jit::fast_map<IRInstruction*, TrackedInstr>& rcInsts) {
1111   FTRACE(1, "OptimizeCatchBlocks:vvvvvvvvvvvvvvvvvvvv\n");
1112   SCOPE_EXIT { FTRACE(1, "OptimizeCatchBlocks:^^^^^^^^^^^^^^^^^^^^\n"); };
1113   for (auto block : blocks) {
1114     if (block->back().is(EndCatch) &&
1115         block->back().extra<EndCatch>()->mode !=
1116           EndCatchData::CatchMode::SideExit &&
1117         block->front().is(BeginCatch)) {
1118       processCatchBlock(unit, state, block, uses, rcInsts);
1119     }
1120   }
1121 }
1122
1123 void optimizeConcats(jit::vector<IRInstruction*>& concats,
1124                      DceState& state,
1125                      IRUnit& unit,
1126                      UseCounts& uses,
1127                      jit::fast_map<IRInstruction*, TrackedInstr>& rcInsts) {
1128   FTRACE(1, "OptimizeConcats:vvvvvvvvvvvvvvvvvvvv\n");
1129   SCOPE_EXIT { FTRACE(1, "OptimizeConcats:^^^^^^^^^^^^^^^^^^^^\n"); };
1130   auto const incref = [&] (auto inst, auto src) {
1131     auto const blk = inst->block();
1132     auto const ins = unit.gen(IncRef, inst->bcctx(), src);
1133     blk->insert(blk->iteratorTo(inst), ins);
1134     state[ins].setLive();
1135     ++uses[src];
1136     FTRACE(3, "Adding {}\n", ins->toString());
1137   };
1138   auto const decref = [&] (auto inst, auto src) {
1139     auto const blk = inst->block();
1140     auto const ins = unit.gen(DecRef, inst->bcctx(), DecRefData{}, src);
1141     blk->insert(blk->iteratorTo(inst), ins);
1142     state[ins].setLive();
1143     ++uses[src];
1144     FTRACE(3, "Adding {}\n", ins->toString());
1145   };
1146   auto const combine = [&] (auto inst, auto inst_prev,
1147                             auto src1, auto src2, auto src3) {
1148     /*
1149      * ~~ Converting ~~
1150      * t1 = ConcatStrStr a b (implicit Decref a)
1151      * DecRef b
1152      * t2 = ConcatStrStr t1 c (implicit Decref t1)
1153      * DecRef c
1154      *
1155      * to
1156      *
1157      * IncRef a
1158      * IncRef b
1159      * t1 = ConcatStrStr a b (implicit Decref a)
1160      * DecRef b
1161      * t2 = ConcatStr3 a b c (implicit Decref a)
1162      * DecRef b
1163      * DecRef c
1164
1165      * ~~ Converting ~~
1166      * t1 = ConcatStrStr a b (implicit Decref a)
1167      * DecRef b
1168      * t2 = ConcatStrStr c t1 (implicit Decref c)
1169      * DecRef t1
1170      *
1171      * to
1172      *
1173      * IncRef a
1174      * IncRef b
1175      * t1 = ConcatStrStr a b (implicit Decref a)
1176      * DecRef b
1177      * t2 = ConcatStr3 c a b (implicit Decref c)
1178      * DecRef a
1179      * DecRef b
1180      * DecRef t1
1181      *
1182      * We need to make sure refcounts are correct. We do this by increffing
1183      * the sources of the first ConcatStrStr and then decreffing them after
1184      * ConcatStr3 unless ConcatStr3 already consumes the reference
1185      *
1186      * Note that later stages of DCE will kill the extra ConcatStrStr and the
1187      * refcounting.
1188      */
1189     assertx(inst_prev->is(ConcatStrStr));
1190     assertx(inst->is(ConcatStrStr));
1191     if (uses[inst_prev->dst()] == 1 + rcInsts[inst_prev].decs.size() +
1192                                       rcInsts[inst_prev].stores.size()) {
1193       FTRACE(3, "Combining {} into {}",
1194              inst_prev->toString(), inst->toString());
1195       auto next = inst->next();
1196       unit.replace(inst, ConcatStr3, inst->taken(), src1, src2, src3);
1197       inst->setNext(next);
1198       FTRACE(3, " and got {}\n", inst->toString());
1199       state[inst].setLive();
1200       --uses[inst_prev->dst()];
1201       ++uses[inst_prev->src(0)];
1202       ++uses[inst_prev->src(1)];
1203       // Incref the first source since the first ConcatStrStr controls
1204       // its refcount
1205       incref(inst_prev, inst_prev->src(0));
1206       incref(inst_prev, inst_prev->src(1));
1207       // ConcatStr3 ends the blocks, so insert the decrefs to the next block
1208       assertx(inst->next() && !inst->next()->empty());
1209       decref(&inst->next()->front(), src2);
1210       if (src3 == inst_prev->src(1)) decref(&inst->next()->front(), src3);
1211     }
1212   };
1213
1214   for (auto& inst : concats) {
1215     if (!inst->is(ConcatStrStr)) continue;
1216     auto const src1 = inst->src(0);
1217     auto const src2 = inst->src(1);
1218     if (src1->inst()->is(ConcatStrStr)) {
1219       combine(inst, src1->inst(),
1220               src1->inst()->src(0), src1->inst()->src(1), src2);
1221     } else if (src2->inst()->is(ConcatStrStr)) {
1222       combine(inst, src2->inst(),
1223               src1, src2->inst()->src(0), src2->inst()->src(1));
1224     }
1225   }
1226 }
1227
1228 ////////////////////////////////////////////////////////////////////////////////
1229
1230 void killInstrAdjustRC(
1231   DceState& state,
1232   IRUnit& unit,
1233   IRInstruction* inst,
1234   jit::vector<IRInstruction*>& decs
1235 ) {
1236   auto const insertDecRef = [&] (auto before, auto src) {
1237     auto const blk = before->block();
1238     auto const ins = unit.gen(DecRef, before->bcctx(), DecRefData{}, src);
1239     blk->insert(blk->iteratorTo(before), ins);
1240     FTRACE(3, "Inserting {} before {} for {}\n",
1241            ins->toString(), before->toString(), inst->toString());
1242     state[ins].setLive();
1243   };
1244   auto anyRemaining = false;
1245   if (inst->consumesReferences()) {
1246     // ConsumesReference inputs that are definitely not moved can
1247     // simply be decreffed as a replacement for the dead consumesref
1248     // instruction
1249     auto srcIx = 0;
1250     for (auto src : inst->srcs()) {
1251       auto const ix = srcIx++;
1252       if (inst->consumesReference(ix) && src->type().maybe(TCounted)) {
1253         if (inst->mayMoveReference(ix)) {
1254           anyRemaining = true;
1255           continue;
1256         }
1257         insertDecRef(inst, src);
1258       }
1259     }
1260   }
1261   for (auto dec : decs) {
1262     auto replaced = dec->src(0) != inst->dst();
1263     auto srcIx = 0;
1264     if (dec->is(DecReleaseCheck)) {
1265       if (inst->is(ConstructClosure) && inst->src(0)->type().maybe(TCounted)) {
1266         assertx(!replaced);
1267         assertx(anyRemaining);
1268         assertx(inst->mayMoveReference(0));
1269
1270         // While the closure is going to be released via ReleaseShallow it will
1271         // still be responsible for releasing the captured context.
1272         insertDecRef(dec, inst->src(0));
1273       }
1274     } else if (anyRemaining) {
1275       assertx(dec->is(DecRef));
1276       // The remaining inputs might be moved, so may need to survive
1277       // until this instruction is decreffed
1278       for (auto src : inst->srcs()) {
1279         if (inst->mayMoveReference(srcIx++) && src->type().maybe(TCounted)) {
1280           if (!replaced) {
1281             FTRACE(3, "Converting {} to ", dec->toString());
1282             dec->setSrc(0, src);
1283             FTRACE(3, "{} for {}\n", dec->toString(), inst->toString());
1284             replaced = true;
1285             state[dec].setLive();
1286           } else {
1287             insertDecRef(dec, src);
1288           }
1289         }
1290       }
1291     }
1292     if (!replaced) {
1293       FTRACE(3, "Killing {} for {}\n", dec->toString(), inst->toString());
1294       state[dec].setDead();
1295     }
1296   }
1297   state[inst].setDead();
1298 }
1299
1300 //////////////////////////////////////////////////////////////////////
1301
1302 } // anonymous namespace
1303
1304 void mandatoryDCE(IRUnit& unit) {
1305   if (removeUnreachable(unit)) {
1306     // Removing unreachable incoming edges can change types, so if we changed
1307     // anything we have to reflow to maintain that IR invariant.
1308     reflowTypes(unit);
1309   }
1310   assertx(checkEverything(unit));
1311 }
1312
1313 void fullDCE(IRUnit& unit) {
1314   if (!RuntimeOption::EvalHHIRDeadCodeElim) {
1315     // This portion of DCE cannot be turned off, because it restores IR
1316     // invariants, and callers of fullDCE are allowed to rely on it for that.
1317     return mandatoryDCE(unit);
1318   }
1319
1320   Timer dceTimer(Timer::optimize_dce);
1321
1322   // kill unreachable code and remove any traces that are now empty
1323   auto const blocks = prepareBlocks(unit);
1324
1325   // At this point, all IR invariants must hold, because we've restored the
1326   // only one allowed to be violated before fullDCE in prepareBlocks.
1327   assertx(checkEverything(unit));
1328
1329   // mark the essential instructions and add them to the initial
1330   // work list; this will also mark reachable exit traces. All
1331   // other instructions marked dead.
1332   DceState state(unit, DceFlags());
1333   WorkList wl = initInstructions(unit, blocks, state);
1334
1335   UseCounts uses(unit, 0);
1336   jit::fast_map<IRInstruction*, TrackedInstr> rcInsts;
1337   DefLabelLiveness defLabelLive;
1338   jit::vector<IRInstruction*> concats;
1339
1340   // process the worklist
1341   while (!wl.empty()) {
1342     auto const [inst, defLabelIdx] = wl.back();
1343     wl.pop_back();
1344     assertx(!state[inst].isDead());
1345     // Jmps which feed a DefLabel are dealt with as part of processing
1346     // the DefLabel. They should never appear on the worklist.
1347     assertx(IMPLIES(inst->is(Jmp), inst->numSrcs() == 0));
1348     assertx(IMPLIES(!inst->is(DefLabel), defLabelIdx == 0));
1349
1350     auto const process = [&] (IRInstruction* inst, uint32_t ix) {
1351       if (inst->is(ConcatStrStr)) concats.emplace_back(inst);
1352       auto const src = inst->src(ix);
1353       IRInstruction* srcInst = src->inst();
1354       if (srcInst->op() == DefConst) return;
1355
1356       if (srcInst->producesReference() && canDCE(*srcInst)) {
1357         ++uses[src];
1358         if (inst->is(DecRef, DecReleaseCheck)) {
1359           rcInsts[srcInst].decs.emplace_back(inst);
1360         }
1361         if (inst->is(InitVecElem, InitDictElem, InitStructElem,
1362                      InitStructPositions, ReleaseShallow, StClosureArg)) {
1363           if (ix == 0) rcInsts[srcInst].aux.emplace_back(inst);
1364         }
1365       }
1366
1367       if (srcInst->is(DefLabel)) {
1368         // If the source instruction is a DefLabel, figure out which
1369         // operand this SSATmp corresponds to, and schedule that
1370         // particular operand.
1371         auto dstIdx = 0;
1372         for (; dstIdx < srcInst->numDsts(); dstIdx++) {
1373           if (src == srcInst->dst(dstIdx)) break;
1374         }
1375         assertx(dstIdx != srcInst->numDsts());
1376         // If the operand isn't already live, schedule it.
1377         if (defLabelLive.emplace(std::make_pair(srcInst, dstIdx)).second) {
1378           state[srcInst].setLive();
1379           wl.push_back(std::make_pair(srcInst, dstIdx));
1380         }
1381       } else if (state[srcInst].isDead()) {
1382         state[srcInst].setLive();
1383         wl.push_back(std::make_pair(srcInst, 0));
1384       }
1385     };
1386
1387     if (inst->is(DefLabel)) {
1388       // For a DefLabel operand, look "through" each corresponding Jmp
1389       // and process the source as if we were processing that Jmp.
1390       assertx(defLabelIdx < inst->numDsts());
1391       assertx(defLabelLive.count(std::make_pair(inst, defLabelIdx)));
1392       inst->block()->forEachPred(
1393         [&, inst = inst, defLabelIdx = defLabelIdx] (Block* pred) {
1394           auto& jmp = pred->back();
1395           assertx(jmp.is(Jmp));
1396           assertx(jmp.numSrcs() == inst->numDsts());
1397           state[&jmp].setLive();
1398           process(&jmp, defLabelIdx);
1399         }
1400       );
1401       continue;
1402     }
1403     // For a normal instruction, just process each source
1404     for (uint32_t ix = 0; ix < inst->numSrcs(); ++ix) process(inst, ix);
1405   }
1406
1407   optimizeCatchBlocks(blocks, state, unit, uses, rcInsts);
1408   optimizeConcats(concats, state, unit, uses, rcInsts);
1409
1410   // If every use of a dce-able PRc instruction is a DecRef or PureStore based
1411   // on its dst, then we can kill it, and DecRef any of its consumesReference
1412   // inputs.
1413   for (auto& pair : rcInsts) {
1414     auto& info = pair.second;
1415     auto const trackedUses =
1416       info.decs.size() + info.aux.size() + info.stores.size();
1417     if (uses[pair.first->dst()] != trackedUses) continue;
1418     killInstrAdjustRC(state, unit, pair.first, info.decs);
1419     for (auto inst : info.aux) killInstrAdjustRC(state, unit, inst, info.decs);
1420     for (auto store : info.stores) store->setSrc(1, unit.cns(TInitNull));
1421   }
1422
1423   // Now remove instructions whose state is DEAD.
1424   removeDeadInstructions(unit, state, defLabelLive);
1425
1426   // Kill unreachable catch blocks.
1427   mandatoryDCE(unit);
1428 }
1429
1430 }