Where Online Learning is simpler!

The C and C++ Include Header Files

cat -n /usr/include/wabt/decompiler-ls.h

     1	/*
     2	 * Copyright 2019 WebAssembly Community Group participants
     3	 *
     4	 * Licensed under the Apache License, Version 2.0 (the "License");
     5	 * you may not use this file except in compliance with the License.
     6	 * You may obtain a copy of the License at
     7	 *
     8	 *     http://www.apache.org/licenses/LICENSE-2.0
     9	 *
    10	 * Unless required by applicable law or agreed to in writing, software
    11	 * distributed under the License is distributed on an "AS IS" BASIS,
    12	 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	 * See the License for the specific language governing permissions and
    14	 * limitations under the License.
    15	 */
    16	
    17	#ifndef WABT_DECOMPILER_LS_H_
    18	#define WABT_DECOMPILER_LS_H_
    19	
    20	#include "wabt/decompiler-ast.h"
    21	#include "wabt/string-util.h"
    22	
    23	#include <map>
    24	
    25	namespace wabt {
    26	
    27	// Names starting with "u" are unsigned, the rest are "signed or doesn't matter"
    28	inline const char* GetDecompTypeName(Type t) {
    29	  switch (t) {
    30	    case Type::I8: return "byte";
    31	    case Type::I8U: return "ubyte";
    32	    case Type::I16: return "short";
    33	    case Type::I16U: return "ushort";
    34	    case Type::I32: return "int";
    35	    case Type::I32U: return "uint";
    36	    case Type::I64: return "long";
    37	    case Type::F32: return "float";
    38	    case Type::F64: return "double";
    39	    case Type::V128: return "simd";
    40	    case Type::Func: return "func";
    41	    case Type::FuncRef: return "funcref";
    42	    case Type::ExternRef: return "externref";
    43	    case Type::Void: return "void";
    44	    default: return "ILLEGAL";
    45	  }
    46	}
    47	
    48	inline Type GetMemoryType(Type operand_type, Opcode opc) {
    49	  // TODO: something something SIMD.
    50	  // TODO: this loses information of the type it is read into.
    51	  // That may well not be the biggest deal since that is usually obvious
    52	  // from context, if not, we should probably represent that as a cast around
    53	  // the access, since it should not be part of the field type.
    54	  if (operand_type == Type::I32 || operand_type == Type::I64) {
    55	    auto name = std::string_view(opc.GetName());
    56	    // FIXME: change into a new column in opcode.def instead?
    57	    auto is_unsigned = name.substr(name.size() - 2) == "_u";
    58	    switch (opc.GetMemorySize()) {
    59	      case 1: return is_unsigned ? Type::I8U : Type::I8;
    60	      case 2: return is_unsigned ? Type::I16U : Type::I16;
    61	      case 4: return is_unsigned ? Type::I32U : Type::I32;
    62	    }
    63	  }
    64	  return operand_type;
    65	}
    66	
    67	// Track all loads and stores inside a single function, to be able to detect
    68	// struct layouts we can use to annotate variables with, to make code more
    69	// readable.
    70	struct LoadStoreTracking {
    71	  struct LSAccess {
    72	    Address byte_size = 0;
    73	    Type type = Type::Any;
    74	    Address align = 0;
    75	    uint32_t idx = 0;
    76	    bool is_uniform = true;
    77	  };
    78	
    79	  struct LSVar {
    80	    std::map<uint64_t, LSAccess> accesses;
    81	    bool struct_layout = true;
    82	    Type same_type = Type::Any;
    83	    Address same_align = kInvalidAddress;
    84	    Opcode last_opc;
    85	  };
    86	
    87	  void Track(const Node& n) {
    88	    for (auto& c : n.children) {
    89	      Track(c);
    90	    }
    91	    switch (n.etype) {
    92	      case ExprType::Load: {
    93	        auto& le = *cast<LoadExpr>(n.e);
    94	        LoadStore(le.offset, le.opcode, le.opcode.GetResultType(), le.align,
    95	                  n.children[0]);
    96	        break;
    97	      }
    98	      case ExprType::Store: {
    99	        auto& se = *cast<StoreExpr>(n.e);
   100	        LoadStore(se.offset, se.opcode, se.opcode.GetParamType2(), se.align,
   101	                  n.children[0]);
   102	        break;
   103	      }
   104	      default:
   105	        break;
   106	    }
   107	  }
   108	
   109	  const std::string AddrExpName(const Node& addr_exp) const {
   110	    // TODO: expand this to more kinds of address expressions.
   111	    switch (addr_exp.etype) {
   112	      case ExprType::LocalGet:
   113	        return cast<LocalGetExpr>(addr_exp.e)->var.name();
   114	        break;
   115	      case ExprType::LocalTee:
   116	        return cast<LocalTeeExpr>(addr_exp.e)->var.name();
   117	        break;
   118	      default:
   119	        return "";
   120	    }
   121	  }
   122	
   123	  void LoadStore(uint64_t offset,
   124	                 Opcode opc,
   125	                 Type type,
   126	                 Address align,
   127	                 const Node& addr_exp) {
   128	    auto byte_size = opc.GetMemorySize();
   129	    type = GetMemoryType(type, opc);
   130	    // We want to associate memory ops of a certain offset & size as being
   131	    // relative to a uniquely identifiable pointer, such as a local.
   132	    auto name = AddrExpName(addr_exp);
   133	    if (name.empty()) {
   134	      return;
   135	    }
   136	    auto& var = vars[name];
   137	    auto& access = var.accesses[offset];
   138	    // Check if previous access at this offset (if any) is of same size
   139	    // and type (see Checklayouts below).
   140	    if (access.byte_size && ((access.byte_size != byte_size) ||
   141	                             (access.type != type) || (access.align != align)))
   142	      access.is_uniform = false;
   143	    // Also exclude weird alignment accesses from structs.
   144	    if (!opc.IsNaturallyAligned(align))
   145	      access.is_uniform = false;
   146	    access.byte_size = byte_size;
   147	    access.type = type;
   148	    access.align = align;
   149	    // Additionally, check if all accesses are to the same type, so
   150	    // if layout check fails, we can at least declare it as pointer to
   151	    // a type.
   152	    if ((var.same_type == type || var.same_type == Type::Any) &&
   153	        (var.same_align == align || var.same_align == kInvalidAddress)) {
   154	      var.same_type = type;
   155	      var.same_align = align;
   156	      var.last_opc = opc;
   157	    } else {
   158	      var.same_type = Type::Void;
   159	      var.same_align = kInvalidAddress;
   160	    }
   161	  }
   162	
   163	  void CheckLayouts() {
   164	    // Here we check if the set of accesses we have collected form a sequence
   165	    // we could declare as a struct, meaning they are properly aligned,
   166	    // contiguous, and have no overlaps between different types and sizes.
   167	    // We do this because an int access of size 2 at offset 0 followed by
   168	    // a float access of size 4 at offset 4 can compactly represented as a
   169	    // struct { short, float }, whereas something that reads from overlapping
   170	    // or discontinuous offsets would need a more complicated syntax that
   171	    // involves explicit offsets.
   172	    // We assume that the bulk of memory accesses are of this very regular kind,
   173	    // so we choose not to even emit struct layouts for irregular ones,
   174	    // given that they are rare and confusing, and thus do not benefit from
   175	    // being represented as if they were structs.
   176	    for (auto& var : vars) {
   177	      if (var.second.accesses.size() == 1) {
   178	        // If we have just one access, this is better represented as a pointer
   179	        // than a struct.
   180	        var.second.struct_layout = false;
   181	        continue;
   182	      }
   183	      uint64_t cur_offset = 0;
   184	      uint32_t idx = 0;
   185	      for (auto& access : var.second.accesses) {
   186	        access.second.idx = idx++;
   187	        if (!access.second.is_uniform) {
   188	          var.second.struct_layout = false;
   189	          break;
   190	        }
   191	        // Align to next access: all elements are expected to be aligned to
   192	        // a memory address thats a multiple of their own size.
   193	        auto mask = static_cast<uint64_t>(access.second.byte_size - 1);
   194	        cur_offset = (cur_offset + mask) & ~mask;
   195	        if (cur_offset != access.first) {
   196	          var.second.struct_layout = false;
   197	          break;
   198	        }
   199	        cur_offset += access.second.byte_size;
   200	      }
   201	    }
   202	  }
   203	
   204	  std::string IdxToName(uint32_t idx) const {
   205	    return IndexToAlphaName(idx);  // TODO: more descriptive names?
   206	  }
   207	
   208	  std::string GenAlign(Address align, Opcode opc) const {
   209	    return opc.IsNaturallyAligned(align) ? "" : cat("@", std::to_string(align));
   210	  }
   211	
   212	  std::string GenTypeDecl(const std::string& name) const {
   213	    auto it = vars.find(name);
   214	    if (it == vars.end()) {
   215	      return "";
   216	    }
   217	    if (it->second.struct_layout) {
   218	      std::string s = "{ ";
   219	      for (auto& access : it->second.accesses) {
   220	        if (access.second.idx) {
   221	          s += ", ";
   222	        }
   223	        s += IdxToName(access.second.idx);
   224	        s += ':';
   225	        s += GetDecompTypeName(access.second.type);
   226	      }
   227	      s += " }";
   228	      return s;
   229	    }
   230	    // We don't have a struct layout, or the struct has just one field,
   231	    // so maybe we can just declare it as a pointer to one type?
   232	    if (it->second.same_type != Type::Void) {
   233	      return cat(GetDecompTypeName(it->second.same_type), "_ptr",
   234	                 GenAlign(it->second.same_align, it->second.last_opc));
   235	    }
   236	    return "";
   237	  }
   238	
   239	  std::string GenAccess(uint64_t offset, const Node& addr_exp) const {
   240	    auto name = AddrExpName(addr_exp);
   241	    if (name.empty()) {
   242	      return "";
   243	    }
   244	    auto it = vars.find(name);
   245	    if (it == vars.end()) {
   246	      return "";
   247	    }
   248	    if (it->second.struct_layout) {
   249	      auto ait = it->second.accesses.find(offset);
   250	      assert(ait != it->second.accesses.end());
   251	      return IdxToName(ait->second.idx);
   252	    }
   253	    // Not a struct, see if it is a typed pointer.
   254	    if (it->second.same_type != Type::Void) {
   255	      return "*";
   256	    }
   257	    return "";
   258	  }
   259	
   260	  void Clear() { vars.clear(); }
   261	
   262	  std::map<std::string, LSVar> vars;
   263	};
   264	
   265	}  // namespace wabt
   266	
   267	#endif  // WABT_DECOMPILER_LS_H_