Update from https://crrev.com/306655

sandbox/linux/seccomp-bpf/codegen.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sandbox/linux/seccomp-bpf/codegen.h"
 
 #include <linux/filter.h>
 
 #include <limits>
 #include <utility>
@@ skipping 31 matching lines @@
 //      sequences.
 
 namespace sandbox {
 
 // kBranchRange is the maximum value that can be stored in
 // sock_filter's 8-bit jt and jf fields.
 const size_t kBranchRange = std::numeric_limits<uint8_t>::max();
 
 const CodeGen::Node CodeGen::kNullNode;
 
-CodeGen::CodeGen() : program_(), memos_() {
+CodeGen::CodeGen() : program_(), equivalent_(), memos_() {
 }
 
 CodeGen::~CodeGen() {
 }
 
 void CodeGen::Compile(CodeGen::Node head, Program* out) {
   DCHECK(out);
   out->assign(program_.rbegin() + Offset(head), program_.rend());
 }
 
@@ skipping 11 matching lines @@
   return *node;
 }
 
 CodeGen::Node CodeGen::AppendInstruction(uint16_t code,
                                          uint32_t k,
                                          Node jt,
                                          Node jf) {
   if (BPF_CLASS(code) == BPF_JMP) {
     CHECK_NE(BPF_JA, BPF_OP(code)) << "CodeGen inserts JAs as needed";
 
-    // We need to check |jt| twice because it might get pushed
-    // out-of-range by appending a jump for |jf|.
-    jt = WithinRange(jt, kBranchRange);
+    // Optimally adding jumps is rather tricky, so we use a quick
+    // approximation: by artificially reducing |jt|'s range, |jt| will
+    // stay within its true range even if we add a jump for |jf|.
+    jt = WithinRange(jt, kBranchRange - 1);
     jf = WithinRange(jf, kBranchRange);
-    jt = WithinRange(jt, kBranchRange);
     return Append(code, k, Offset(jt), Offset(jf));
   }
 
   CHECK_EQ(kNullNode, jf) << "Non-branch instructions shouldn't provide jf";
   if (BPF_CLASS(code) == BPF_RET) {
     CHECK_EQ(kNullNode, jt) << "Return instructions shouldn't provide jt";
   } else {
     // For non-branch/non-return instructions, execution always
     // proceeds to the next instruction; so we need to arrange for
     // that to be |jt|.
     jt = WithinRange(jt, 0);
+    CHECK_EQ(0U, Offset(jt)) << "ICE: Failed to setup next instruction";
   }
   return Append(code, k, 0, 0);
 }
 
 CodeGen::Node CodeGen::WithinRange(Node target, size_t range) {
-  if (Offset(target) > range) {
-    // TODO(mdempsky): If |range > 0|, we might be able to reuse an
-    // existing instruction within that range.
-
-    // TODO(mdempsky): If |target| is a branch or return, it might be
-    // possible to duplicate that instruction rather than jump to it.
-
-    // Fall back to emitting a jump instruction.
-    target = Append(BPF_JMP | BPF_JA, Offset(target), 0, 0);
+  // Just use |target| if it's already within range.
+  if (Offset(target) <= range) {
+    return target;
   }
 
-  CHECK_LE(Offset(target), range) << "ICE: Failed to bring target within range";
-  return target;
+  // Alternatively, look for an equivalent instruction within range.
+  if (Offset(equivalent_.at(target)) <= range) {
+    return equivalent_.at(target);
+  }
+
+  // Otherwise, fall back to emitting a jump instruction.
+  Node jump = Append(BPF_JMP | BPF_JA, Offset(target), 0, 0);
+  equivalent_.at(target) = jump;
+  return jump;
 }
 
 CodeGen::Node CodeGen::Append(uint16_t code, uint32_t k, size_t jt, size_t jf) {
   if (BPF_CLASS(code) == BPF_JMP && BPF_OP(code) != BPF_JA) {
     CHECK_LE(jt, kBranchRange);
     CHECK_LE(jf, kBranchRange);
   } else {
     CHECK_EQ(0U, jt);
     CHECK_EQ(0U, jf);
   }
 
   CHECK_LT(program_.size(), static_cast<size_t>(BPF_MAXINSNS));
+  CHECK_EQ(program_.size(), equivalent_.size());
+
+  Node res = program_.size();
   program_.push_back(sock_filter{code, jt, jf, k});
-  return program_.size() - 1;
+  equivalent_.push_back(res);
+  return res;
 }
 
 size_t CodeGen::Offset(Node target) const {
   CHECK_LT(target, program_.size()) << "Bogus offset target node";
   return (program_.size() - 1) - target;
 }
 
 // TODO(mdempsky): Move into a general base::Tuple helper library.
 bool CodeGen::MemoKeyLess::operator()(const MemoKey& lhs,
                                       const MemoKey& rhs) const {
   if (lhs.a != rhs.a)
     return lhs.a < rhs.a;
   if (lhs.b != rhs.b)
     return lhs.b < rhs.b;
   if (lhs.c != rhs.c)
     return lhs.c < rhs.c;
   if (lhs.d != rhs.d)
     return lhs.d < rhs.d;
   return false;
 }
 
 }  // namespace sandbox