[clangd] Split DecisionForest Evaluate() into one func per tree.

[usaxena95]

Summary

This allows us MSAN to instrument this function. Previous version is not
instrumentable due to it shear volume.

[usaxena95]

Minor formatting fixes.

[adamcz]

clang-tools-extra/clangd/quality/CompletionModelCodegen.py

168

Why are these member functions? Why not keep them in .cc file only, in anonymous namespace?

I wonder if that will make compiler inline them and then bring back msan issues though.

[usaxena95]

clang-tools-extra/clangd/quality/CompletionModelCodegen.py

168

Why are these member functions? Why not keep them in .cc file only, in anonymous namespace?

We will need to add getters for member variables (hoping they would be inlined).
SG ?
(Or make the members public o_O ?)

I wonder if that will make compiler inline them and then bring back MSAN issues though.

I think we can disable that using LLVM_ATTRIBUTE_NOINLINE

[usaxena95]

Addressed comments: Move the evaluate functions to anonymous namespace.

clang-tools-extra/clangd/quality/CompletionModelCodegen.py

 """Code generator for Code Completion Model Inference.
 
 Tool runs on the Decision Forest model defined in {model} directory.
-It generates two files: {output_dir}/{filename}.h and {output_dir}/{filename}.cpp 
+It generates two files: {output_dir}/{filename}.h and {output_dir}/{filename}.cpp
 The generated files defines the Example class named {cpp_class} having all the features as class members.
 The generated runtime provides an `Evaluate` function which can be used to score a code completion candidate.
 """
 
 import argparse
 import json
 import struct
 

 
 
 def header_guard(filename):
     '''Returns the header guard for the generated header.'''
     return "GENERATED_DECISION_FOREST_MODEL_%s_H" % filename.upper()
 
 
 def boost_node(n, label, next_label):
-    """Returns code snippet for a leaf/boost node.
-    Adds value of leaf to the score and jumps to the root of the next tree."""
-    return "%s: Score += %s; goto %s;" % (
-            label, n['score'], next_label)
+    """Returns code snippet for a leaf/boost node."""
+    return "%s: return %s;" % (label, n['score'])
 
 
 def if_greater_node(n, label, next_label):
     """Returns code snippet for a if_greater node.
-    Jumps to true_label if the Example feature (NUMBER) is greater than the threshold. 
-    Comparing integers is much faster than comparing floats. Assuming floating points 
+    Jumps to true_label if the Example feature (NUMBER) is greater than the threshold.
+    Comparing integers is much faster than comparing floats. Assuming floating points
     are represented as IEEE 754, it order-encodes the floats to integers before comparing them.
     Control falls through if condition is evaluated to false."""
     threshold = n["threshold"]
-    return "%s: if (E.%s >= %s /*%s*/) goto %s;" % (
-            label, n['feature'], order_encode(threshold), threshold, next_label)
+    return "%s: if (%s >= %s /*%s*/) goto %s;" % (
 
 
 def if_member_node(n, label, next_label):
     """Returns code snippet for a if_member node.
-    Jumps to true_label if the Example feature (ENUM) is present in the set of enum values 
+    Jumps to true_label if the Example feature (ENUM) is present in the set of enum values
     described in the node.
     Control falls through if condition is evaluated to false."""
     members = '|'.join([
         "BIT(%s_type::%s)" % (n['feature'], member)
         for member in n["set"]
     ])
-    return "%s: if (E.%s & (%s)) goto %s;" % (
-            label, n['feature'], members, next_label)
+    return "%s: if (%s & (%s)) goto %s;" % (
 
 
 def node(n, label, next_label):
     """Returns code snippet for the node."""
     return {
         'boost': boost_node,
         'if_greater': if_greater_node,
         'if_member': if_member_node,
def tree(t, tree_num, node_num):
     -   Conditional node evaluates a condition. If true, it jumps to the true node/child.
         Code is generated using pre-order traversal of the tree considering
         false node as the first child. Therefore the false node is always the
         immediately next label.
     -   Leaf node adds the value to the score and jumps to the next tree.
     """
     label = "t%d_n%d" % (tree_num, node_num)
     code = []
-    if node_num == 0:
-        code.append("t%d:" % tree_num)
 
     if t["operation"] == "boost":
         code.append(node(t, label=label, next_label="t%d" % (tree_num + 1)))
         return code, 1
 
     false_code, false_size = tree(
         t['else'], tree_num=tree_num, node_num=node_num+1)
 
     true_node_num = node_num+false_size+1
     true_label = "t%d_n%d" % (tree_num, true_node_num)
 
     true_code, true_size = tree(
         t['then'], tree_num=tree_num, node_num=true_node_num)
 
     code.append(node(t, label=label, next_label=true_label))
 
     return code+false_code+true_code, 1+false_size+true_size
 
 
-def gen_header_code(features_json, cpp_class, filename):
+def gen_header_code(features_json, cpp_class, filename, num_trees):
     """Returns code for header declaring the inference runtime.
 
     Declares the Example class named {cpp_class} inside relevant namespaces.
-    The Example class contains all the features as class members. This 
+    The Example class contains all the features as class members. This
     class can be used to represent a code completion candidate.
     Provides `float Evaluate()` function which can be used to score the Example.
     """
     setters = []
     for f in features_json:
         feature = f["name"]
         if f["kind"] == "NUMBER":
             # Floats are order-encoded to integers for faster comparison.
def gen_header_code(features_json, cpp_class, filename, num_trees):
     # Class members represent all the features of the Example.
     class_members = ["uint32_t %s = 0;" % f['name'] for f in features_json]
 
     nline = "\n  "
     guard = header_guard(filename)
     return """#ifndef %s
 #define %s
 #include <cstdint>
-#include "llvm/Support/Compiler.h"
 
 %s
 class %s {
 public:
   %s
 
 private:
   %s
 
   // Produces an integer that sorts in the same order as F.
   // That is: a < b <==> orderEncode(a) < orderEncode(b).
   static uint32_t OrderEncode(float F);
+
+  // Evaluation functions for each tree.
+%s
+
   friend float Evaluate(const %s&);
 };
 
-// The function may have large number of lines of code. MSAN
-// build times out in such case.
-LLVM_NO_SANITIZE("memory")
 float Evaluate(const %s&);
 %s
 #endif // %s
 """ % (guard, guard, cpp_class.ns_begin(), cpp_class.name, nline.join(setters),
-        nline.join(class_members), cpp_class.name, cpp_class.name,
-        cpp_class.ns_end(), guard)
+        nline.join(class_members),
+        nline.join(["  float EvaluateTree%d() const;" % tree_num
+                    for tree_num in range(num_trees)]),
+        cpp_class.name, cpp_class.name, cpp_class.ns_end(), guard)
 
 
 def order_encode(v):
     i = struct.unpack('<I', struct.pack('<f', v))[0]
     TopBit = 1 << 31
     # IEEE 754 floats compare like sign-magnitude integers.
     if (i & TopBit):  # Negative float
         return (1 << 32) - i  # low half of integers, order reversed.
     return TopBit + i  # top half of integers
 
 
-def evaluate_func(forest_json, cpp_class):
-    """Generates code for `float Evaluate(const {Example}&)` function.
-    The generated function can be used to score an Example."""
-    code = "float Evaluate(const %s& E) {\n" % cpp_class.name
-    lines = []
-    lines.append("float Score = 0;")
+def evaluate_funcs(forest_json, cpp_class):
+    """Generates evaluation functions for each tree and combines them in
+    `float Evaluate(const {Example}&)` function. This function can be 
+    used to score an Example."""
+    
+    code = ""
+
+    # Generate evaluation function of each tree.
     tree_num = 0
     for tree_json in forest_json:
-        lines.extend(tree(tree_json, tree_num=tree_num, node_num=0)[0])
-        lines.append("")
+        code += "float %s::EvaluateTree%d() const {\n" % (
+            cpp_class.name, tree_num)
+        code += "  " + \
+            "  \n".join(
+                tree(tree_json, tree_num=tree_num, node_num=0)[0]) + "\n"
+        code += "}\n\n"
         tree_num += 1
 
-    lines.append("t%s: // No such tree." % len(forest_json))
-    lines.append("return Score;")
-    code += "  " + "\n  ".join(lines)
-    code += "\n}"
+    # Combine the scores of all trees in the final function.
+    code += "float Evaluate(const %s& E) {\n" % cpp_class.name
+    code += "  float Score = 0;\n"
+    for tree_num in range(len(forest_json)):
+        code += "  Score += E.EvaluateTree%d();\n" % tree_num
+    code += "  return Score;\n"
+    code += "}\n"
+
     return code
 
 
 def gen_cpp_code(forest_json, features_json, filename, cpp_class):
     """Generates code for the .cpp file."""
     # Headers
     # Required by OrderEncode(float F).
     angled_include = [
uint32_t %s::OrderEncode(float F) {
   if (U & TopBit)    // Negative float.
     return 0 - U;    // Map onto the low half of integers, order reversed.
   return U + TopBit; // Positive floats map onto the high half of integers.
 }
 
 %s
 %s
 """ % (nl.join(angled_include), nl.join(quoted_include), cpp_class.ns_begin(),
-       using_decls, cpp_class.name, evaluate_func(forest_json, cpp_class),
+       using_decls, cpp_class.name, evaluate_funcs(forest_json, cpp_class),
        cpp_class.ns_end())
 
 
 def main():
     parser = argparse.ArgumentParser('DecisionForestCodegen')
     parser.add_argument('--filename', help='output file name.')
     parser.add_argument('--output_dir', help='output directory.')
     parser.add_argument('--model', help='path to model directory.')
with open(cpp_file, 'w+t') as output_cc:
         output_cc.write(
             gen_cpp_code(forest_json=forest_json,
                          features_json=features_json,
                          filename=filename,
                          cpp_class=cpp_class))
 
     with open(header_file, 'w+t') as output_h:
         output_h.write(gen_header_code(
-            features_json=features_json, cpp_class=cpp_class, filename=filename))
+            features_json=features_json,
+            cpp_class=cpp_class,
+            filename=filename,
+            num_trees=len(forest_json)))
 
 
 if __name__ == '__main__':
     main()