From 9fd9deac0ad181b4f8bab175645de9e22d01b59e Mon Sep 17 00:00:00 2001 From: Jordan DeLong Date: Fri, 28 Feb 2014 15:23:21 -0800 Subject: [PATCH] Hook up array types to iterator instructions Reviewed By: @dariorussi Differential Revision: D1197599 --- hphp/hhbbc/analyze.cpp | 1 + hphp/hhbbc/interp-state.cpp | 65 +++++++++++++++++++++++++++++--- hphp/hhbbc/interp-state.h | 12 ++++++ hphp/hhbbc/interp.h | 58 ++++++++++++++++++++++------ hphp/hhbbc/type-system.cpp | 35 +++++++++++++++++ hphp/hhbbc/type-system.h | 8 ++++ hphp/test/slow/hhbbc/iter_001.php | 10 +++++ hphp/test/slow/hhbbc/iter_001.php.expect | 2 + hphp/test/slow/hhbbc/iter_002.php | 5 +++ hphp/test/slow/hhbbc/iter_002.php.expect | 0 hphp/test/slow/hhbbc/iter_003.php | 11 ++++++ hphp/test/slow/hhbbc/iter_003.php.expect | 6 +++ 12 files changed, 197 insertions(+), 16 deletions(-) create mode 100644 hphp/test/slow/hhbbc/iter_001.php create mode 100644 hphp/test/slow/hhbbc/iter_001.php.expect create mode 100644 hphp/test/slow/hhbbc/iter_002.php create mode 100644 hphp/test/slow/hhbbc/iter_002.php.expect create mode 100644 hphp/test/slow/hhbbc/iter_003.php create mode 100644 hphp/test/slow/hhbbc/iter_003.php.expect diff --git a/hphp/hhbbc/analyze.cpp b/hphp/hhbbc/analyze.cpp index 58e9d74d9a2..b5ca08829ce 100644 --- a/hphp/hhbbc/analyze.cpp +++ b/hphp/hhbbc/analyze.cpp @@ -40,6 +40,7 @@ State entry_state(const Index& index, ret.initialized = true; ret.thisAvailable = index.lookup_this_available(ctx.func); ret.locals.resize(ctx.func->locals.size()); + ret.iters.resize(ctx.func->iters.size()); auto locId = uint32_t{0}; for (; locId < ctx.func->params.size(); ++locId) { diff --git a/hphp/hhbbc/interp-state.cpp b/hphp/hhbbc/interp-state.cpp index 24a7cae03cf..d778af79320 100644 --- a/hphp/hhbbc/interp-state.cpp +++ b/hphp/hhbbc/interp-state.cpp @@ -20,12 +20,54 @@ #include "folly/Format.h" #include "folly/Conv.h" +#include "hphp/util/match.h" #include "hphp/hhbbc/analyze.h" namespace HPHP { namespace HHBBC { ////////////////////////////////////////////////////////////////////// +namespace { + +template +bool merge_into(Iter& dst, const Iter& src, JoinOp join) { + return match( + dst, + [&] (UnknownIter) { return false; }, + [&] (TrackedIter& diter) { + return match( + src, + [&] (UnknownIter) { + dst = UnknownIter {}; + return true; + }, + [&] (const TrackedIter& siter) { + auto k1 = join(diter.kv.first, siter.kv.first); + auto k2 = join(diter.kv.second, siter.kv.second); + auto const changed = k1 != diter.kv.first || k2 != diter.kv.second; + diter.kv = std::make_pair(std::move(k1), std::move(k2)); + return changed; + } + ); + } + ); +} + +std::string show(const Iter& iter) { + return match( + iter, + [&] (UnknownIter) { return "unk"; }, + [&] (const TrackedIter& ti) { + return folly::format("{}, {}", show(ti.kv.first), + show(ti.kv.second)).str(); + } + ); +} + +} + +////////////////////////////////////////////////////////////////////// + bool operator==(const ActRec& a, const ActRec& b) { auto const fsame = a.func.hasValue() != b.func.hasValue() ? false : @@ -50,6 +92,7 @@ State without_stacks(const State& src) { ret.initialized = src.initialized; ret.thisAvailable = src.thisAvailable; ret.locals = src.locals; + ret.iters = src.iters; return ret; } @@ -131,6 +174,7 @@ bool merge_impl(State& dst, const State& src, JoinOp join) { assert(src.initialized); assert(dst.locals.size() == src.locals.size()); + assert(dst.iters.size() == src.iters.size()); assert(dst.stack.size() == src.stack.size()); assert(dst.fpiStack.size() == src.fpiStack.size()); @@ -158,6 +202,12 @@ bool merge_impl(State& dst, const State& src, JoinOp join) { } } + for (auto i = size_t{0}; i < dst.iters.size(); ++i) { + if (merge_into(dst.iters[i], src.iters[i], join)) { + changed = true; + } + } + for (auto i = size_t{0}; i < dst.fpiStack.size(); ++i) { if (merge_into(dst.fpiStack[i], src.fpiStack[i])) { changed = true; @@ -209,22 +259,27 @@ std::string state_string(const php::Func& f, const State& st) { ret = "state:\n"; if (f.cls) { - ret += folly::format("thisAvailable({})\n", st.thisAvailable).str(); + folly::format(&ret, "thisAvailable({})\n", st.thisAvailable); } + for (auto i = size_t{0}; i < st.locals.size(); ++i) { - ret += folly::format("${: <8} :: {}\n", + folly::format(&ret, "${: <8} :: {}\n", f.locals[i]->name ? std::string(f.locals[i]->name->data()) : folly::format("", i).str(), show(st.locals[i]) - ).str(); + ); + } + + for (auto i = size_t{0}; i < st.iters.size(); ++i) { + folly::format(&ret, "iter {: <2} :: {}\n", i, show(st.iters[i])); } for (auto i = size_t{0}; i < st.stack.size(); ++i) { - ret += folly::format("stk[{:02}] :: {}\n", + folly::format(&ret, "stk[{:02}] :: {}\n", i, show(st.stack[i]) - ).str(); + ); } return ret; diff --git a/hphp/hhbbc/interp-state.h b/hphp/hhbbc/interp-state.h index 7ab5e093585..0ccd348c3b3 100644 --- a/hphp/hhbbc/interp-state.h +++ b/hphp/hhbbc/interp-state.h @@ -20,6 +20,8 @@ #include #include +#include + #include "folly/Optional.h" #include "hphp/hhbbc/index.h" @@ -49,12 +51,22 @@ struct ActRec { }; /* + * State of an iterator in the program. + */ +struct UnknownIter {}; +struct TrackedIter { std::pair kv; }; +using Iter = boost::variant< UnknownIter + , TrackedIter + >; + +/* * A program state at a position in a php::Block. */ struct State { bool initialized = false; bool thisAvailable = false; std::vector locals; + std::vector iters; std::vector stack; std::vector fpiStack; }; diff --git a/hphp/hhbbc/interp.h b/hphp/hhbbc/interp.h index 2bcc93707f2..6ae4a953680 100644 --- a/hphp/hhbbc/interp.h +++ b/hphp/hhbbc/interp.h @@ -1385,13 +1385,17 @@ struct InterpStepper : boost::static_visitor { void operator()(const bc::DecodeCufIter&) { popC(); } void operator()(const bc::IterInit& op) { - popC(); + auto const t1 = popC(); // Take the branch before setting locals if the iter is already // empty, but after popping. Similar for the other IterInits // below. + freeIter(op.iter1); m_propagate(*op.target, m_state); - setLoc(op.loc3, TInitCell); + auto ity = iter_types(t1); + setLoc(op.loc3, ity.second); + setIter(op.iter1, TrackedIter { std::move(ity) }); } + void operator()(const bc::MIterInit& op) { popV(); m_propagate(*op.target, m_state); @@ -1399,11 +1403,15 @@ struct InterpStepper : boost::static_visitor { } void operator()(const bc::IterInitK& op) { - popC(); + auto const t1 = popC(); + freeIter(op.iter1); m_propagate(*op.target, m_state); - setLoc(op.loc3, TInitCell); - setLoc(op.loc4, TInitCell); + auto ity = iter_types(t1); + setLoc(op.loc3, ity.second); + setLoc(op.loc4, ity.first); + setIter(op.iter1, TrackedIter { std::move(ity) }); } + void operator()(const bc::MIterInitK& op) { popV(); m_propagate(*op.target, m_state); @@ -1419,6 +1427,7 @@ struct InterpStepper : boost::static_visitor { // ref. setLocRaw(op.loc3, TInitGen); } + void operator()(const bc::WIterInitK& op) { popC(); m_propagate(*op.target, m_state); @@ -1427,19 +1436,36 @@ struct InterpStepper : boost::static_visitor { } void operator()(const bc::IterNext& op) { + match( + m_state.iters[op.iter1->id], + [&] (UnknownIter) { this->setLoc(op.loc3, TInitCell); }, + [&] (const TrackedIter& ti) { this->setLoc(op.loc3, ti.kv.second); } + ); m_propagate(*op.target, m_state); - setLoc(op.loc3, TInitCell); + freeIter(op.iter1); } + void operator()(const bc::MIterNext& op) { m_propagate(*op.target, m_state); setLocRaw(op.loc3, TRef); } void operator()(const bc::IterNextK& op) { + match( + m_state.iters[op.iter1->id], + [&] (UnknownIter) { + this->setLoc(op.loc3, TInitCell); + this->setLoc(op.loc4, TInitCell); + }, + [&] (const TrackedIter& ti) { + this->setLoc(op.loc3, ti.kv.second); + this->setLoc(op.loc4, ti.kv.first); + } + ); m_propagate(*op.target, m_state); - setLoc(op.loc3, TInitCell); - setLoc(op.loc4, TInitCell); + freeIter(op.iter1); } + void operator()(const bc::MIterNextK& op) { m_propagate(*op.target, m_state); setLocRaw(op.loc3, TRef); @@ -1450,17 +1476,19 @@ struct InterpStepper : boost::static_visitor { m_propagate(*op.target, m_state); setLocRaw(op.loc3, TInitGen); } + void operator()(const bc::WIterNextK& op) { m_propagate(*op.target, m_state); setLocRaw(op.loc3, TInitGen); setLoc(op.loc4, TInitCell); } - void operator()(const bc::IterFree&) { nothrow(); } - void operator()(const bc::MIterFree&) { nothrow(); } - void operator()(const bc::CIterFree&) { nothrow(); } + void operator()(const bc::IterFree& op) { nothrow(); freeIter(op.iter1); } + void operator()(const bc::MIterFree& op) { nothrow(); freeIter(op.iter1); } + void operator()(const bc::CIterFree& op) { nothrow(); freeIter(op.iter1); } void operator()(const bc::IterBreak& op) { + for (auto& kv : op.iterTab) freeIter(kv.second); m_propagate(*op.target, m_state); } @@ -3327,6 +3355,14 @@ private: // locals return borrow(m_ctx.func->locals[id]); } +private: // iterators + void setIter(borrowed_ptr iter, Iter iterState) { + m_state.iters[iter->id] = std::move(iterState); + } + void freeIter(borrowed_ptr iter) { + m_state.iters[iter->id] = UnknownIter {}; + } + private: // $this void setThisAvailable() { FTRACE(2, " setThisAvailable\n"); diff --git a/hphp/hhbbc/type-system.cpp b/hphp/hhbbc/type-system.cpp index b3684b3e3a6..7954907db6c 100644 --- a/hphp/hhbbc/type-system.cpp +++ b/hphp/hhbbc/type-system.cpp @@ -2016,6 +2016,41 @@ Type array_newelem(const Type& arr, const Type& val) { return array_newelem_key(arr, val).first; } +std::pair iter_types(const Type& iterable) { + if (!iterable.subtypeOf(TArr) || !is_specialized_array(iterable)) { + return { TInitCell, TInitCell }; + } + + switch (iterable.m_dataTag) { + case DataTag::None: + if (iterable.subtypeOf(TSArr)) { + return { TInitUnc, TInitUnc }; + } + return { TInitCell, TInitCell }; + case DataTag::Str: + case DataTag::Obj: + case DataTag::Int: + case DataTag::Dbl: + case DataTag::Cls: + always_assert(0); + case DataTag::ArrVal: + if (auto const mn = toDArrMapN(iterable.m_data.aval)) { + return { mn->key, mn->val }; + } + return { TInitUnc, TInitUnc }; + case DataTag::ArrPacked: + return { TInt, packed_values(*iterable.m_data.apacked) }; + case DataTag::ArrPackedN: + return { TInt, iterable.m_data.apackedn->type }; + case DataTag::ArrStruct: + return { TSStr, struct_values(*iterable.m_data.astruct) }; + case DataTag::ArrMapN: + return { iterable.m_data.amapn->key, iterable.m_data.amapn->val }; + } + + not_reached(); +} + ////////////////////////////////////////////////////////////////////// }} diff --git a/hphp/hhbbc/type-system.h b/hphp/hhbbc/type-system.h index e2038aadcca..a1922a3f048 100644 --- a/hphp/hhbbc/type-system.h +++ b/hphp/hhbbc/type-system.h @@ -350,6 +350,7 @@ private: friend Type array_elem(const Type&, const Type&); friend Type array_set(Type, const Type&, const Type&); friend std::pair array_newelem_key(const Type&, const Type&); + friend std::pair iter_types(const Type&); private: union Data { @@ -748,6 +749,13 @@ Type array_newelem(const Type& arr, const Type& val); */ std::pair array_newelem_key(const Type& arr, const Type& val); +/* + * Return the best known key and value type for iteration of the + * supplied type. This is only intended for non-mutable iteration, so + * the returned types are at worst InitCell. + */ +std::pair iter_types(const Type&); + ////////////////////////////////////////////////////////////////////// }} diff --git a/hphp/test/slow/hhbbc/iter_001.php b/hphp/test/slow/hhbbc/iter_001.php new file mode 100644 index 00000000000..7b05a4d075e --- /dev/null +++ b/hphp/test/slow/hhbbc/iter_001.php @@ -0,0 +1,10 @@ +heh(); + } +} +foo(); diff --git a/hphp/test/slow/hhbbc/iter_001.php.expect b/hphp/test/slow/hhbbc/iter_001.php.expect new file mode 100644 index 00000000000..1e1b91e1e6e --- /dev/null +++ b/hphp/test/slow/hhbbc/iter_001.php.expect @@ -0,0 +1,2 @@ +hi +hi \ No newline at end of file diff --git a/hphp/test/slow/hhbbc/iter_002.php b/hphp/test/slow/hhbbc/iter_002.php new file mode 100644 index 00000000000..b719f967e37 --- /dev/null +++ b/hphp/test/slow/hhbbc/iter_002.php @@ -0,0 +1,5 @@ + new A, 'bar' => new A); + foreach ($x as $k => $v) { + var_dump($k); + var_dump($v); + } +} +foo(); diff --git a/hphp/test/slow/hhbbc/iter_003.php.expect b/hphp/test/slow/hhbbc/iter_003.php.expect new file mode 100644 index 00000000000..7d92b5b5273 --- /dev/null +++ b/hphp/test/slow/hhbbc/iter_003.php.expect @@ -0,0 +1,6 @@ +string(3) "foo" +object(A)#1 (0) { +} +string(3) "bar" +object(A)#2 (0) { +} \ No newline at end of file -- 2.11.4.GIT