diff --git a/src/eval_env.cc b/src/eval_env.cc
index 796a326..675bb83 100644
--- a/src/eval_env.cc
+++ b/src/eval_env.cc
@@ -31,22 +31,22 @@
   bindings_[key] = val;
 }
 
-void BindingEnv::AddRule(const Rule* rule) {
+void BindingEnv::AddRule(Rule* rule) {
   assert(LookupRuleCurrentScope(rule->name()) == NULL);
-  rules_[rule->name()] = rule;
+  rules_.emplace(rule->name(), std::unique_ptr<Rule>(rule));
 }
 
 const Rule* BindingEnv::LookupRuleCurrentScope(const string& rule_name) {
-  map<string, const Rule*>::iterator i = rules_.find(rule_name);
-  if (i == rules_.end())
+  auto it = rules_.find(rule_name);
+  if (it == rules_.end())
     return NULL;
-  return i->second;
+  return it->second.get();
 }
 
 const Rule* BindingEnv::LookupRule(const string& rule_name) {
-  map<string, const Rule*>::iterator i = rules_.find(rule_name);
-  if (i != rules_.end())
-    return i->second;
+  auto it = rules_.find(rule_name);
+  if (it != rules_.end())
+    return it->second.get();
   if (parent_)
     return parent_->LookupRule(rule_name);
   return NULL;
@@ -78,10 +78,6 @@
       var == "msvc_deps_prefix";
 }
 
-const map<string, const Rule*>& BindingEnv::GetRules() const {
-  return rules_;
-}
-
 string BindingEnv::LookupWithFallback(const string& var,
                                       const EvalString* eval,
                                       Env* env) {
diff --git a/src/eval_env.h b/src/eval_env.h
index 677dc21..2c69d94 100644
--- a/src/eval_env.h
+++ b/src/eval_env.h
@@ -16,6 +16,7 @@
 #define NINJA_EVAL_ENV_H_
 
 #include <map>
+#include <memory>
 #include <string>
 #include <vector>
 
@@ -57,10 +58,13 @@
 
 /// An invocable build command and associated metadata (description, etc.).
 struct Rule {
-  explicit Rule(const std::string& name) : name_(name) {}
+  Rule(StringPiece name)
+      : name_(name.str_, name.len_), is_phony_(name_ == "phony") {}
 
   const std::string& name() const { return name_; }
 
+  bool is_phony() const { return is_phony_; }
+
   void AddBinding(const std::string& key, const EvalString& val);
 
   static bool IsReservedBinding(const std::string& var);
@@ -72,6 +76,7 @@
   friend struct ManifestParser;
 
   std::string name_;
+  bool is_phony_;
   typedef std::map<std::string, EvalString> Bindings;
   Bindings bindings_;
 };
@@ -82,13 +87,22 @@
   BindingEnv() : parent_(NULL) {}
   explicit BindingEnv(BindingEnv* parent) : parent_(parent) {}
 
+  BindingEnv(const BindingEnv&) = delete;
+  BindingEnv& operator=(const BindingEnv&) = delete;
+
+  BindingEnv(BindingEnv&&) noexcept = default;
+  BindingEnv& operator=(BindingEnv&&) noexcept = default;
+
   virtual ~BindingEnv() {}
   virtual std::string LookupVariable(const std::string& var);
 
-  void AddRule(const Rule* rule);
+  /// Add a new rule, takes ownership.
+  void AddRule(Rule* rule);
   const Rule* LookupRule(const std::string& rule_name);
   const Rule* LookupRuleCurrentScope(const std::string& rule_name);
-  const std::map<std::string, const Rule*>& GetRules() const;
+
+  using RuleMapType = std::map<std::string, std::unique_ptr<const Rule>>;
+  const RuleMapType& GetRules() const { return rules_; }
 
   void AddBinding(const std::string& key, const std::string& val);
 
@@ -102,7 +116,7 @@
 
 private:
   std::map<std::string, std::string> bindings_;
-  std::map<std::string, const Rule*> rules_;
+  RuleMapType rules_;
   BindingEnv* parent_;
 };
 
diff --git a/src/graph.cc b/src/graph.cc
index 2132388..2ea491e 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -589,7 +589,7 @@
 }
 
 bool Edge::is_phony() const {
-  return rule_ == &State::kPhonyRule;
+  return rule_->is_phony();
 }
 
 bool Edge::use_console() const {
diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index c4b2980..c52925c 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -143,7 +143,7 @@
   if (env_->LookupRuleCurrentScope(name) != NULL)
     return lexer_.Error("duplicate rule '" + name + "'", err);
 
-  Rule* rule = new Rule(name);  // XXX scoped_ptr
+  auto rule = std::unique_ptr<Rule>(new Rule(name));
 
   while (lexer_.PeekToken(Lexer::INDENT)) {
     string key;
@@ -169,7 +169,7 @@
   if (rule->bindings_["command"].empty())
     return lexer_.Error("expected 'command =' line", err);
 
-  env_->AddRule(rule);
+  env_->AddRule(rule.release());
   return true;
 }
 
diff --git a/src/manifest_parser_test.cc b/src/manifest_parser_test.cc
index c5a1fe8..e41d8ae 100644
--- a/src/manifest_parser_test.cc
+++ b/src/manifest_parser_test.cc
@@ -51,7 +51,7 @@
 "build result: cat in_1.cc in-2.O\n"));
 
   ASSERT_EQ(3u, state.bindings_.GetRules().size());
-  const Rule* rule = state.bindings_.GetRules().begin()->second;
+  const Rule* rule = state.bindings_.GetRules().begin()->second.get();
   EXPECT_EQ("cat", rule->name());
   EXPECT_EQ("[cat ][$in][ > ][$out]",
             rule->GetBinding("command")->Serialize());
@@ -84,7 +84,7 @@
 "  #comment\n"));
 
   ASSERT_EQ(2u, state.bindings_.GetRules().size());
-  const Rule* rule = state.bindings_.GetRules().begin()->second;
+  const Rule* rule = state.bindings_.GetRules().begin()->second.get();
   EXPECT_EQ("cat", rule->name());
   Edge* edge = state.GetNode("result", 0)->in_edge();
   EXPECT_TRUE(edge->GetBindingBool("restat"));
@@ -117,7 +117,7 @@
 "  rspfile=out.rsp\n"));
 
   ASSERT_EQ(2u, state.bindings_.GetRules().size());
-  const Rule* rule = state.bindings_.GetRules().begin()->second;
+  const Rule* rule = state.bindings_.GetRules().begin()->second.get();
   EXPECT_EQ("cat_rsp", rule->name());
   EXPECT_EQ("[cat ][$rspfile][ > ][$out]",
             rule->GetBinding("command")->Serialize());
@@ -134,7 +134,7 @@
 "  rspfile=out.rsp\n"));
 
   ASSERT_EQ(2u, state.bindings_.GetRules().size());
-  const Rule* rule = state.bindings_.GetRules().begin()->second;
+  const Rule* rule = state.bindings_.GetRules().begin()->second.get();
   EXPECT_EQ("cat_rsp", rule->name());
   EXPECT_EQ("[cat ][$in_newline][ > ][$out]",
             rule->GetBinding("command")->Serialize());
@@ -195,7 +195,7 @@
 " d e f\n"));
 
   ASSERT_EQ(2u, state.bindings_.GetRules().size());
-  const Rule* rule = state.bindings_.GetRules().begin()->second;
+  const Rule* rule = state.bindings_.GetRules().begin()->second.get();
   EXPECT_EQ("link", rule->name());
   EXPECT_EQ("[foo bar baz]", rule->GetBinding("command")->Serialize());
 }
diff --git a/src/ninja.cc b/src/ninja.cc
index 7ccf164..c08b20e 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -658,14 +658,12 @@
 
   // Print rules
 
-  typedef map<string, const Rule*> Rules;
-  const Rules& rules = state_.bindings_.GetRules();
-  for (Rules::const_iterator i = rules.begin(); i != rules.end(); ++i) {
-    printf("%s", i->first.c_str());
+  for (const auto& pair : state_.bindings_.GetRules()) {
+    printf("%s", pair.first.c_str());
     if (print_description) {
-      const Rule* rule = i->second;
-      const EvalString* description = rule->GetBinding("description");
-      if (description != NULL) {
+    const Rule* rule = pair.second.get();
+    const EvalString* description = rule->GetBinding("description");
+    if (description != NULL) {
         printf(": %s", description->Unparse().c_str());
       }
     }
diff --git a/src/state.cc b/src/state.cc
index 39f0dff..cc78d03 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -67,10 +67,9 @@
   delayed_.clear();
 }
 
-const Rule State::kPhonyRule("phony");
-
 State::State() {
-  bindings_.AddRule(&kPhonyRule);
+  phony_rule_ = new Rule("phony");
+  bindings_.AddRule(phony_rule_);
   default_pool_ = new Pool("", 0);
   console_pool_ = new Pool("console", 1);
   AddPool(default_pool_);
diff --git a/src/state.h b/src/state.h
index b8ff095..958463b 100644
--- a/src/state.h
+++ b/src/state.h
@@ -100,8 +100,6 @@
 
 /// Global state (file status) for a single run.
 struct State {
-  static const Rule kPhonyRule;
-
   State();
 
   ~State();
@@ -124,6 +122,12 @@
   /// implicitly.
   Pool* console_pool() const;
 
+  /// Return pointer to phony rule. This one is always created implicitly.
+  const Rule* phony_rule() const { return phony_rule_; }
+
+  /// Allocate new Rule instance.
+  Rule* NewRule(StringPiece name);
+
   Edge* AddEdge(const Rule* rule);
 
   Node* GetNode(StringPiece path, uint64_t slash_bits);
@@ -167,6 +171,7 @@
   /// NOTE: This owns all Edge instances.
   std::vector<Edge*> edges_;
 
+  Rule* phony_rule_ = nullptr;
   BindingEnv bindings_;
   std::vector<Node*> defaults_;
 };