hphp/runtime/vm/jit/vasm-dead.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 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/vasm.h"
  18
  19 #include "hphp/runtime/vm/jit/timer.h"
  20 #include "hphp/runtime/vm/jit/vasm-instr.h"
  21 #include "hphp/runtime/vm/jit/vasm-print.h"
  22 #include "hphp/runtime/vm/jit/vasm-reg.h"
  23 #include "hphp/runtime/vm/jit/vasm-unit.h"
  24 #include "hphp/runtime/vm/jit/vasm-util.h"
  25 #include "hphp/runtime/vm/jit/vasm-visit.h"
  26
  27 #include <boost/dynamic_bitset.hpp>
  28
  29 #include <algorithm>
  30
  31 TRACE_SET_MOD(vasm);
  32
  33 namespace HPHP { namespace jit {
  34
  35 namespace {
  36 typedef boost::dynamic_bitset<> LiveSet;
  37 bool effectful(Vinstr& inst) {
  38   switch (inst.op) {
  39     case Vinstr::absdbl:
  40     case Vinstr::addl:
  41     case Vinstr::addli:
  42     case Vinstr::addq:
  43     case Vinstr::addqi:
  44     case Vinstr::addsd:
  45     case Vinstr::andb:
  46     case Vinstr::andbi:
  47     case Vinstr::andl:
  48     case Vinstr::andli:
  49     case Vinstr::andq:
  50     case Vinstr::andqi:
  51     case Vinstr::andqi64:
  52     case Vinstr::cloadq:
  53     case Vinstr::cmovb:
  54     case Vinstr::cmovw:
  55     case Vinstr::cmovl:
  56     case Vinstr::cmovq:
  57     case Vinstr::cmpb:
  58     case Vinstr::cmpbi:
  59     case Vinstr::cmpbim:
  60     case Vinstr::cmpbm:
  61     case Vinstr::cmpw:
  62     case Vinstr::cmpwi:
  63     case Vinstr::cmpl:
  64     case Vinstr::cmpli:
  65     case Vinstr::cmplim:
  66     case Vinstr::cmplm:
  67     case Vinstr::cmpq:
  68     case Vinstr::cmpqi:
  69     case Vinstr::cmpqim:
  70     case Vinstr::cmpqm:
  71     case Vinstr::cmpsd:
  72     case Vinstr::cmpwim:
  73     case Vinstr::cmpwm:
  74     case Vinstr::copy:
  75     case Vinstr::copy2:
  76     case Vinstr::copyargs:
  77     case Vinstr::csincb:
  78     case Vinstr::csincw:
  79     case Vinstr::csincl:
  80     case Vinstr::csincq:
  81     case Vinstr::cvtsi2sd:
  82     case Vinstr::cvtsi2sdm:
  83     case Vinstr::cvttsd2siq:
  84     case Vinstr::decl:
  85     case Vinstr::decq:
  86     case Vinstr::defvmretdata:
  87     case Vinstr::defvmrettype:
  88     case Vinstr::defvmsp:
  89     case Vinstr::divint:
  90     case Vinstr::divsd:
  91     case Vinstr::fcmpo:
  92     case Vinstr::fcmpu:
  93     case Vinstr::fctidz:
  94     case Vinstr::fcvtzs:
  95     case Vinstr::imul:
  96     case Vinstr::incl:
  97     case Vinstr::incq:
  98     case Vinstr::incw:
  99     case Vinstr::ldimmb:
 100     case Vinstr::ldimml:
 101     case Vinstr::ldimmq:
 102     case Vinstr::ldimmw:
 103     case Vinstr::lea:
 104     case Vinstr::lead:
 105     case Vinstr::leap:
 106     case Vinstr::load:
 107     case Vinstr::loadb:
 108     case Vinstr::loadl:
 109     case Vinstr::loadqd:
 110     case Vinstr::loadqp:
 111     case Vinstr::loadsd:
 112     case Vinstr::loadtqb:
 113     case Vinstr::loadtql:
 114     case Vinstr::loadups:
 115     case Vinstr::loadw:
 116     case Vinstr::loadzbl:
 117     case Vinstr::loadzbq:
 118     case Vinstr::loadzlq:
 119     case Vinstr::loadsbq:
 120     case Vinstr::mflr:
 121     case Vinstr::movb:
 122     case Vinstr::movl:
 123     case Vinstr::movsbl:
 124     case Vinstr::movswl:
 125     case Vinstr::movsbq:
 126     case Vinstr::movswq:
 127     case Vinstr::movslq:
 128     case Vinstr::movtqb:
 129     case Vinstr::movtdb:
 130     case Vinstr::movtdq:
 131     case Vinstr::movtql:
 132     case Vinstr::movtqw:
 133     case Vinstr::movw:
 134     case Vinstr::movzbw:
 135     case Vinstr::movzbl:
 136     case Vinstr::movzbq:
 137     case Vinstr::movzwl:
 138     case Vinstr::movzwq:
 139     case Vinstr::movzlq:
 140     case Vinstr::mrs:
 141     case Vinstr::mulsd:
 142     case Vinstr::neg:
 143     case Vinstr::nop:
 144     case Vinstr::not:
 145     case Vinstr::notb:
 146     case Vinstr::orq:
 147     case Vinstr::orqi:
 148     case Vinstr::roundsd:
 149     case Vinstr::sar:
 150     case Vinstr::sarq:
 151     case Vinstr::sarqi:
 152     case Vinstr::setcc:
 153     case Vinstr::shl:
 154     case Vinstr::shlli:
 155     case Vinstr::shlq:
 156     case Vinstr::shlqi:
 157     case Vinstr::shrli:
 158     case Vinstr::shrqi:
 159     case Vinstr::sqrtsd:
 160     case Vinstr::srem:
 161     case Vinstr::subl:
 162     case Vinstr::subli:
 163     case Vinstr::subq:
 164     case Vinstr::subqi:
 165     case Vinstr::subsd:
 166     case Vinstr::testb:
 167     case Vinstr::testbi:
 168     case Vinstr::testbim:
 169     case Vinstr::testw:
 170     case Vinstr::testwi:
 171     case Vinstr::testl:
 172     case Vinstr::testli:
 173     case Vinstr::testlim:
 174     case Vinstr::testq:
 175     case Vinstr::testqi:
 176     case Vinstr::testqim:
 177     case Vinstr::testqm:
 178     case Vinstr::testwim:
 179     case Vinstr::ucomisd:
 180     case Vinstr::unpcklpd:
 181     case Vinstr::ubfmli:
 182     case Vinstr::xorb:
 183     case Vinstr::xorbi:
 184     case Vinstr::xorl:
 185     case Vinstr::xorq:
 186     case Vinstr::xorqi:
 187       return false;
 188
 189     case Vinstr::addwm:
 190     case Vinstr::addlm:
 191     case Vinstr::addlim:
 192     case Vinstr::addqmr:
 193     case Vinstr::addqrm:
 194     case Vinstr::addqim:
 195     case Vinstr::andbim:
 196     case Vinstr::bindaddr:
 197     case Vinstr::bindjcc:
 198     case Vinstr::bindjmp:
 199     case Vinstr::funcguard:
 200     case Vinstr::debugguardjmp:
 201     case Vinstr::inlinestart:
 202     case Vinstr::inlineend:
 203     case Vinstr::popframe:
 204     case Vinstr::pushframe:
 205     case Vinstr::call:
 206     case Vinstr::callunpack:
 207     case Vinstr::callfaststub:
 208     case Vinstr::callm:
 209     case Vinstr::callphp:
 210     case Vinstr::callr:
 211     case Vinstr::calls:
 212     case Vinstr::callstub:
 213     case Vinstr::calltc:
 214     case Vinstr::contenter:
 215     case Vinstr::cqo:
 216     case Vinstr::debugtrap:
 217     case Vinstr::declm:
 218     case Vinstr::decqm:
 219     case Vinstr::decqmlock:
 220     case Vinstr::fallback:
 221     case Vinstr::fallbackcc:
 222     case Vinstr::fallthru:
 223     case Vinstr::idiv:
 224     case Vinstr::inclm:
 225     case Vinstr::incqm:
 226     case Vinstr::incwm:
 227     case Vinstr::inittc:
 228     case Vinstr::jcc:
 229     case Vinstr::jcci:
 230     case Vinstr::jmp:
 231     case Vinstr::jmpi:
 232     case Vinstr::jmpm:
 233     case Vinstr::jmpr:
 234     case Vinstr::landingpad:
 235     case Vinstr::leavetc:
 236     case Vinstr::loadstubret:
 237     case Vinstr::mcprep:
 238     case Vinstr::msr:
 239     case Vinstr::mtlr:
 240     case Vinstr::nothrow:
 241     case Vinstr::orbim:
 242     case Vinstr::orlim:
 243     case Vinstr::orqim:
 244     case Vinstr::orwim:
 245     case Vinstr::phidef:
 246     case Vinstr::phijcc:
 247     case Vinstr::phijmp:
 248     case Vinstr::phplogue:
 249     case Vinstr::phpret:
 250     case Vinstr::pop:
 251     case Vinstr::popm:
 252     case Vinstr::popf:
 253     case Vinstr::popp:
 254     case Vinstr::poppm:
 255     case Vinstr::push:
 256     case Vinstr::pushm:
 257     case Vinstr::pushf:
 258     case Vinstr::pushp:
 259     case Vinstr::pushpm:
 260     case Vinstr::resumetc:
 261     case Vinstr::ret:
 262     case Vinstr::retransopt:
 263     case Vinstr::store:
 264     case Vinstr::storeb:
 265     case Vinstr::storebi:
 266     case Vinstr::storeups:
 267     case Vinstr::storel:
 268     case Vinstr::storeli:
 269     case Vinstr::storeqi:
 270     case Vinstr::storesd:
 271     case Vinstr::storew:
 272     case Vinstr::storewi:
 273     case Vinstr::stublogue:
 274     case Vinstr::stubret:
 275     case Vinstr::stubtophp:
 276     case Vinstr::stubunwind:
 277     case Vinstr::syncpoint:
 278     case Vinstr::syncvmret:
 279     case Vinstr::syncvmrettype:
 280     case Vinstr::syncvmsp:
 281     case Vinstr::tailcallphp:
 282     case Vinstr::tailcallstub:
 283     case Vinstr::trap:
 284     case Vinstr::unwind:
 285     case Vinstr::vcall:
 286     case Vinstr::vcallunpack:
 287     case Vinstr::vinvoke:
 288     case Vinstr::vregrestrict:
 289     case Vinstr::vregunrestrict:
 290     case Vinstr::conjure:
 291     case Vinstr::conjureuse:
 292       return true;
 293   }
 294   always_assert(false);
 295 }
 296 }
 297
 298 // Remove dead instructions by doing a traditional liveness analysis.
 299 // instructions that mutate memory, physical registers, or status flags
 300 // are considered useful. All branches are considered useful.
 301 //
 302 // Given SSA, there's a faster sparse version of this algorithm that marks
 303 // useful instructions in one pass, then transitively marks pure instructions
 304 // that define inputs to useful instructions. However it requires a mapping
 305 // from vreg numbers to the instruction that defines them, and a way to address
 306 // individual instructions.
 307 //
 308 // We could remove useless branches by computing the post-dominator tree and
 309 // RDF(b) for each block; then a branch is only useful if it controls whether
 310 // or not a useful block executes, and useless branches can be forwarded to
 311 // the nearest useful post-dominator.
 312 void removeDeadCode(Vunit& unit) {
 313   Timer timer(Timer::vasm_dce);
 314   auto blocks = sortBlocks(unit);
 315   jit::vector<LiveSet> livein(unit.blocks.size());
 316   LiveSet live(unit.next_vr);
 317
 318   auto pass = [&](bool mutate) {
 319     bool changed = false;
 320     for (auto blockIt = blocks.end(); blockIt != blocks.begin();) {
 321       auto b = *--blockIt;
 322       auto& block = unit.blocks[b];
 323       live.reset();
 324       for (auto s : succs(block)) {
 325         if (!livein[s].empty()) {
 326           live |= livein[s];
 327         }
 328       }
 329       for (auto i = block.code.end(); i != block.code.begin();) {
 330         auto& inst = *--i;
 331         auto useful = effectful(inst);
 332         visitDefs(unit, inst, [&](Vreg r) {
 333           if (r.isPhys() || live.test(r)) {
 334             useful = true;
 335             live.reset(r);
 336           }
 337         });
 338         if (useful) {
 339           visitUses(unit, inst, [&](Vreg r) {
 340             live.set(r);
 341           });
 342         } else if (mutate) {
 343           inst = nop{};
 344           changed = true;
 345         }
 346       }
 347       if (mutate) {
 348         assertx(live == livein[b]);
 349       } else {
 350         if (live != livein[b]) {
 351           livein[b] = live;
 352           changed = true;
 353         }
 354       }
 355     }
 356     return changed;
 357   };
 358
 359   // analyze until livein reaches a fixed point
 360   while (pass(false)) {}
 361   auto const changed = pass(true);
 362   removeTrivialNops(unit);
 363   if (changed) {
 364     printUnit(kVasmDCELevel, "after vasm-dead", unit);
 365   }
 366 }
 367
 368 /*
 369  * A very simple dead code elimination pass that just removes trivial nop
 370  * instructions.  We run this before any other passes because it allows
 371  * code-gen to create things like self-copies or self-lea's without affect on
 372  * optimizations downstream.  (In particular early passes like optimizeExits
 373  * that are looking for specific vasm sequences inside of a block.)
 374  */
 375 void removeTrivialNops(Vunit& unit) {
 376   for (auto& b : unit.blocks) {
 377     b.code.erase(
 378       std::remove_if(
 379         begin(b.code), end(b.code),
 380         is_trivial_nop
 381       ),
 382       end(b.code)
 383     );
 384   }
 385 }
 386
 387 }}