dexter/experimental.cc - platform/tools/dexter - Gitiles

 /*
  * Copyright (C) 2017 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "experimental.h"
 #include "slicer/code_ir.h"
 #include "slicer/control_flow_graph.h"
 #include "slicer/dex_ir.h"
 #include "slicer/dex_ir_builder.h"
 #include "slicer/instrumentation.h"

 #include <string.h>
 #include <map>
 #include <memory>
 #include <vector>

 namespace experimental {

 // Rewrites every method through raising to code IR -> back to bytecode
 // (also stress the CFG creation)
 void FullRewrite(std::shared_ptr<ir::DexFile> dex_ir) {
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code != nullptr) {
       lir::CodeIr code_ir(ir_method.get(), dex_ir);
       lir::ControlFlowGraph cfg_compact(&code_ir, false);
       lir::ControlFlowGraph cfg_verbose(&code_ir, true);
       code_ir.Assemble();
     }
   }
 }

 // For every method body in the .dex image, replace invoke-virtual[/range]
 // instances with a invoke-static[/range] to a fictitious Tracer.WrapInvoke(<args...>)
 // WrapInvoke() is a static method which takes the same arguments as the
 // original method plus an explicit "this" argument, and returns the same
 // type as the original method.
 void StressWrapInvoke(std::shared_ptr<ir::DexFile> dex_ir) {
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code == nullptr) {
       continue;
     }

     lir::CodeIr code_ir(ir_method.get(), dex_ir);
     ir::Builder builder(dex_ir);

     // search for invoke-virtual[/range] bytecodes
     //
     // NOTE: we may be removing the current bytecode
     //   from the instructions list so we must use a
     //   different iteration style (it++ is done before
     //   handling *it, not after as in a normal iteration)
     //
     auto it = code_ir.instructions.begin();
     while (it != code_ir.instructions.end()) {
       auto instr = *it++;
       auto bytecode = dynamic_cast<lir::Bytecode*>(instr);
       if (bytecode == nullptr) {
         continue;
       }

       dex::Opcode new_call_opcode = dex::OP_NOP;
       switch (bytecode->opcode) {
         case dex::OP_INVOKE_VIRTUAL:
           new_call_opcode = dex::OP_INVOKE_STATIC;
           break;
         case dex::OP_INVOKE_VIRTUAL_RANGE:
           new_call_opcode = dex::OP_INVOKE_STATIC_RANGE;
           break;
         default:
           // skip instruction ...
           continue;
       }
       assert(new_call_opcode != dex::OP_NOP);

       auto orig_method = bytecode->CastOperand<lir::Method>(1)->ir_method;

       // construct the wrapper method declaration
       std::vector<ir::Type*> param_types;
       param_types.push_back(orig_method->parent);
       if (orig_method->prototype->param_types != nullptr) {
         const auto& orig_param_types = orig_method->prototype->param_types->types;
         param_types.insert(param_types.end(), orig_param_types.begin(), orig_param_types.end());
       }

       auto ir_proto = builder.GetProto(orig_method->prototype->return_type,
                                        builder.GetTypeList(param_types));

       auto ir_method_decl = builder.GetMethodDecl(builder.GetAsciiString("WrapInvoke"),
                                                   ir_proto,
                                                   builder.GetType("LTracer;"));

       auto wraper_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

       // new call bytecode
       auto new_call = code_ir.Alloc<lir::Bytecode>();
       new_call->opcode = new_call_opcode;
       new_call->operands.push_back(bytecode->operands[0]);
       new_call->operands.push_back(wraper_method);
       code_ir.instructions.InsertBefore(bytecode, new_call);

       // remove the old call bytecode
       //
       // NOTE: we can mutate the original bytecode directly
       //  since the instructions can't have multiple references
       //  in the code IR, but for testing purposes we'll do it
       //  the hard way here
       //
       code_ir.instructions.Remove(bytecode);
     }

     code_ir.Assemble();
   }
 }

 // For every method in the .dex image, insert an "entry hook" call
 // to a fictitious method: Tracer.OnEntry(<args...>). OnEntry() has the
 // same argument types as the instrumented method plus an explicit
 // "this" for non-static methods. On entry to the instumented method
 // we'll call OnEntry() with the values of the incoming arguments.
 //
 // NOTE: the entry hook will forward all the incoming arguments
 //   so we need to define an Tracer.OnEntry overload for every method
 //   signature. This means that for very large .dex images, approaching
 //   the 64k method limit, we might not be able to allocate new method declarations.
 //   (which is ok, and a good test case, since this is a stress scenario)
 //
 void StressEntryHook(std::shared_ptr<ir::DexFile> dex_ir) {
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code == nullptr) {
       continue;
     }

     lir::CodeIr code_ir(ir_method.get(), dex_ir);
     ir::Builder builder(dex_ir);

     // 1. construct call target
     std::vector<ir::Type*> param_types;
     if ((ir_method->access_flags & dex::kAccStatic) == 0) {
       param_types.push_back(ir_method->decl->parent);
     }
     if (ir_method->decl->prototype->param_types != nullptr) {
       const auto& orig_param_types = ir_method->decl->prototype->param_types->types;
       param_types.insert(param_types.end(), orig_param_types.begin(), orig_param_types.end());
     }

     auto ir_proto = builder.GetProto(builder.GetType("V"),
                                      builder.GetTypeList(param_types));

     auto ir_method_decl = builder.GetMethodDecl(builder.GetAsciiString("OnEntry"),
                                                 ir_proto,
                                                 builder.GetType("LTracer;"));

     auto target_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

     // 2. argument registers
     auto regs = ir_method->code->registers;
     auto args_count = ir_method->code->ins_count;
     auto args = code_ir.Alloc<lir::VRegRange>(regs - args_count, args_count);

     // 3. call bytecode
     auto call = code_ir.Alloc<lir::Bytecode>();
     call->opcode = dex::OP_INVOKE_STATIC_RANGE;
     call->operands.push_back(args);
     call->operands.push_back(target_method);

     // 4. insert the hook before the first bytecode
     for (auto instr : code_ir.instructions) {
       auto bytecode = dynamic_cast<lir::Bytecode*>(instr);
       if (bytecode == nullptr) {
         continue;
       }
       code_ir.instructions.InsertBefore(bytecode, call);
       break;
     }

     code_ir.Assemble();
   }
 }

 // For every method in the .dex image, insert an "exit hook" call
 // to a fictitious method: Tracer.OnExit(<return value...>).
 // OnExit() is called right before returning from the instrumented
 // method (on the non-exceptional path) and it will be passed the return
 // value, if any. For non-void return types, the return value from OnExit()
 // will also be used as the return value of the instrumented method.
 void StressExitHook(std::shared_ptr<ir::DexFile> dex_ir) {
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code == nullptr) {
       continue;
     }

     lir::CodeIr code_ir(ir_method.get(), dex_ir);
     ir::Builder builder(dex_ir);

     // do we have a void-return method?
     bool return_void =
         ::strcmp(ir_method->decl->prototype->return_type->descriptor->c_str(), "V") == 0;

     // 1. construct call target
     std::vector<ir::Type*> param_types;
     if (!return_void) {
       param_types.push_back(ir_method->decl->prototype->return_type);
     }

     auto ir_proto = builder.GetProto(ir_method->decl->prototype->return_type,
                                      builder.GetTypeList(param_types));

     auto ir_method_decl = builder.GetMethodDecl(builder.GetAsciiString("OnExit"),
                                                 ir_proto,
                                                 builder.GetType("LTracer;"));

     auto target_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

     // 2. find and instrument the return instructions
     for (auto instr : code_ir.instructions) {
       auto bytecode = dynamic_cast<lir::Bytecode*>(instr);
       if (bytecode == nullptr) {
         continue;
       }

       dex::Opcode move_result_opcode = dex::OP_NOP;
       dex::u4 reg = 0;
       int reg_count = 0;

       switch (bytecode->opcode) {
         case dex::OP_RETURN_VOID:
           SLICER_CHECK(return_void);
           break;
         case dex::OP_RETURN:
           SLICER_CHECK(!return_void);
           move_result_opcode = dex::OP_MOVE_RESULT;
           reg = bytecode->CastOperand<lir::VReg>(0)->reg;
           reg_count = 1;
           break;
         case dex::OP_RETURN_OBJECT:
           SLICER_CHECK(!return_void);
           move_result_opcode = dex::OP_MOVE_RESULT_OBJECT;
           reg = bytecode->CastOperand<lir::VReg>(0)->reg;
           reg_count = 1;
           break;
         case dex::OP_RETURN_WIDE:
           SLICER_CHECK(!return_void);
           move_result_opcode = dex::OP_MOVE_RESULT_WIDE;
           reg = bytecode->CastOperand<lir::VRegPair>(0)->base_reg;
           reg_count = 2;
           break;
         default:
           // skip the bytecode...
           continue;
       }

       // the call bytecode
       auto args = code_ir.Alloc<lir::VRegRange>(reg, reg_count);
       auto call = code_ir.Alloc<lir::Bytecode>();
       call->opcode = dex::OP_INVOKE_STATIC_RANGE;
       call->operands.push_back(args);
       call->operands.push_back(target_method);
       code_ir.instructions.InsertBefore(bytecode, call);

       // move result back to the right register
       //
       // NOTE: we're reusing the original return's operand,
       //   which is valid and more efficient than allocating
       //   a new LIR node, but it's also fragile: we need to be
       //   very careful about mutating shared nodes.
       //
       if (move_result_opcode != dex::OP_NOP) {
         auto move_result = code_ir.Alloc<lir::Bytecode>();
         move_result->opcode = move_result_opcode;
         move_result->operands.push_back(bytecode->operands[0]);
         code_ir.instructions.InsertBefore(bytecode, move_result);
       }
     }

     code_ir.Assemble();
   }
 }

 // Test slicer::MethodInstrumenter
 void TestMethodInstrumenter(std::shared_ptr<ir::DexFile> dex_ir) {
   slicer::MethodInstrumenter mi(dex_ir);
   mi.AddTransformation<slicer::EntryHook>(ir::MethodId("LTracer;", "onFooEntry"), true);
   mi.AddTransformation<slicer::EntryHook>(ir::MethodId("LTracer;", "onFooEntry"), false);
   mi.AddTransformation<slicer::ExitHook>(ir::MethodId("LTracer;", "onFooExit"));
   mi.AddTransformation<slicer::DetourVirtualInvoke>(
       ir::MethodId("LBase;", "foo", "(ILjava/lang/String;)I"),
       ir::MethodId("LTracer;", "wrapFoo"));
   mi.AddTransformation<slicer::DetourInterfaceInvoke>(
       ir::MethodId("LIBase;", "bar", "(Ljava/lang/String;)V"),
       ir::MethodId("LTracer;", "wrapBar"));

   auto method1 = ir::MethodId("LTarget;", "foo", "(ILjava/lang/String;)I");
   SLICER_CHECK(mi.InstrumentMethod(method1));

   auto method2 = ir::MethodId("LTarget;", "foo", "(I[[Ljava/lang/String;)Ljava/lang/Integer;");
   SLICER_CHECK(mi.InstrumentMethod(method2));
 }

 // Stress scratch register allocation
 void StressScratchRegs(std::shared_ptr<ir::DexFile> dex_ir) {
   slicer::MethodInstrumenter mi(dex_ir);

   // queue multiple allocations to stress corner cases (various counts and alignments)
   auto t1 = mi.AddTransformation<slicer::AllocateScratchRegs>(1, false);
   auto t2 = mi.AddTransformation<slicer::AllocateScratchRegs>(1, false);
   auto t3 = mi.AddTransformation<slicer::AllocateScratchRegs>(1);
   auto t4 = mi.AddTransformation<slicer::AllocateScratchRegs>(20);

   // apply the transformations to every single method
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code != nullptr) {
       SLICER_CHECK(mi.InstrumentMethod(ir_method.get()));
       SLICER_CHECK(t1->ScratchRegs().size() == 1);
       SLICER_CHECK(t2->ScratchRegs().size() == 1);
       SLICER_CHECK(t3->ScratchRegs().size() == 1);
       SLICER_CHECK(t4->ScratchRegs().size() == 20);
     }
   }
 }

 // Sample code coverage instrumentation: on the entry of every
 // basic block, inject a call to a tracing method:
 //
 //   CodeCoverage.TraceBasicBlock(block_id)
 //
 void CodeCoverage(std::shared_ptr<ir::DexFile> dex_ir) {
   ir::Builder builder(dex_ir);
   slicer::AllocateScratchRegs alloc_regs(1);
   int basic_block_id = 1;

   constexpr const char* kTracerClass = "LCodeCoverage;";

   // create the tracing method declaration
   std::vector<ir::Type*> param_types { builder.GetType("I") };
   auto ir_proto =
       builder.GetProto(builder.GetType("V"),
                        builder.GetTypeList(param_types));
   auto ir_method_decl =
       builder.GetMethodDecl(builder.GetAsciiString("TraceBasicBlock"),
                             ir_proto,
                             builder.GetType(kTracerClass));

   // instrument every method (except for the tracer class methods)
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code == nullptr) {
       continue;
     }

     // don't instrument the methods of the tracer class
     if (std::strcmp(ir_method->decl->parent->descriptor->c_str(), kTracerClass) == 0) {
       continue;
     }

     lir::CodeIr code_ir(ir_method.get(), dex_ir);
     lir::ControlFlowGraph cfg(&code_ir, true);

     // allocate a scratch register
     //
     // NOTE: we're assuming this does not change the CFG!
     //   (this is the case here, but transformations which
     //    alter the basic blocks boundaries or the code flow
     //    would invalidate existing CFGs)
     //
     alloc_regs.Apply(&code_ir);
     dex::u4 scratch_reg = *alloc_regs.ScratchRegs().begin();

     // TODO: handle very "high" registers
     if (scratch_reg > 0xff) {
       printf("WARNING: can't instrument method %s.%s%s\n",
              ir_method->decl->parent->Decl().c_str(),
              ir_method->decl->name->c_str(),
              ir_method->decl->prototype->Signature().c_str());
       continue;
     }

     auto tracing_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

     // instrument each basic block entry point
     for (const auto& block : cfg.basic_blocks) {
       // generate the map of basic blocks
       printf("%8u: mi=%u s=%u e=%u\n",
              static_cast<dex::u4>(basic_block_id),
              ir_method->decl->orig_index,
              block.region.first->offset,
              block.region.last->offset);

       // find first bytecode in the basic block
       lir::Instruction* trace_point = nullptr;
       for (auto instr = block.region.first; instr != nullptr; instr = instr->next) {
         trace_point = dynamic_cast<lir::Bytecode*>(instr);
         if (trace_point != nullptr || instr == block.region.last) {
           break;
         }
       }
       SLICER_CHECK(trace_point != nullptr);

       // special case: don't separate 'move-result-<kind>' from the preceding invoke
       auto opcode = static_cast<lir::Bytecode*>(trace_point)->opcode;
       if (opcode == dex::OP_MOVE_RESULT ||
           opcode == dex::OP_MOVE_RESULT_WIDE ||
           opcode == dex::OP_MOVE_RESULT_OBJECT) {
         trace_point = trace_point->next;
       }

       // arg_reg = block_id
       auto load_block_id = code_ir.Alloc<lir::Bytecode>();
       load_block_id->opcode = dex::OP_CONST;
       load_block_id->operands.push_back(code_ir.Alloc<lir::VReg>(scratch_reg));
       load_block_id->operands.push_back(code_ir.Alloc<lir::Const32>(basic_block_id));
       code_ir.instructions.InsertBefore(trace_point, load_block_id);

       // call the tracing method
       auto trace_call = code_ir.Alloc<lir::Bytecode>();
       trace_call->opcode = dex::OP_INVOKE_STATIC_RANGE;
       trace_call->operands.push_back(code_ir.Alloc<lir::VRegRange>(scratch_reg, 1));
       trace_call->operands.push_back(tracing_method);
       code_ir.instructions.InsertBefore(trace_point, trace_call);

       ++basic_block_id;
     }

     code_ir.Assemble();
   }
 }

 // Stress the roundtrip: EncodedMethod -> MethodId -> FindMethod -> EncodedMethod
 // NOTE: until we start indexing methods this test is slow on debug builds + large .dex images
 void StressFindMethod(std::shared_ptr<ir::DexFile> dex_ir) {
   ir::Builder builder(dex_ir);
   int method_count = 0;
   for (auto& ir_method : dex_ir->encoded_methods) {
     auto decl = ir_method->decl;
     auto signature = decl->prototype->Signature();
     auto class_descriptor = decl->parent->descriptor;
     ir::MethodId method_id(class_descriptor->c_str(), decl->name->c_str(), signature.c_str());
     SLICER_CHECK(builder.FindMethod(method_id) == ir_method.get());
     ++method_count;
   }
   printf("Everything looks fine, found %d methods.\n", method_count);
 }

 static void PrintHistogram(const std::map<int, int> histogram, const char* name) {
   constexpr int kHistogramWidth = 100;
   int max_count = 0;
   for (const auto& kv : histogram) {
     max_count = std::max(max_count, kv.second);
   }
   printf("\nHistogram: %s [max_count=%d]\n\n", name, max_count);
   for (const auto& kv : histogram) {
     printf("%6d [ %3d ] ", kv.second, kv.first);
     int hist_len = static_cast<int>(static_cast<double>(kv.second) / max_count * kHistogramWidth);
     for (int i = 0; i <= hist_len; ++i) {
       printf("*");
     }
     printf("\n");
   }
 }

 // Builds a histogram of registers count per method
 void RegsHistogram(std::shared_ptr<ir::DexFile> dex_ir) {
   std::map<int, int> regs_histogram;
   std::map<int, int> param_histogram;
   std::map<int, int> extra_histogram;
   for (auto& ir_method : dex_ir->encoded_methods) {
     if (ir_method->code != nullptr) {
       const int regs = ir_method->code->registers;
       const int ins =  ir_method->code->ins_count;
       SLICER_CHECK(regs >= ins);
       regs_histogram[regs]++;
       param_histogram[ins]++;
       extra_histogram[regs - ins]++;
     }
   }
   PrintHistogram(regs_histogram, "Method registers");
   PrintHistogram(param_histogram, "Method parameter registers");
   PrintHistogram(regs_histogram, "Method extra registers (total - parameters)");
 }

 void ListExperiments(std::shared_ptr<ir::DexFile> dex_ir);

 using Experiment = void (*)(std::shared_ptr<ir::DexFile>);

 // the registry of available experiments
 std::map<std::string, Experiment> experiments_registry = {
     { "list_experiments", &ListExperiments },
     { "full_rewrite", &FullRewrite },
     { "stress_entry_hook", &StressEntryHook },
     { "stress_exit_hook", &StressExitHook },
     { "stress_wrap_invoke", &StressWrapInvoke },
     { "test_method_instrumenter", &TestMethodInstrumenter },
     { "stress_find_method", &StressFindMethod },
     { "stress_scratch_regs", &StressScratchRegs },
     { "regs_histogram", &RegsHistogram },
     { "code_coverage", &CodeCoverage },
 };

 // Lists all the registered experiments
 void ListExperiments(std::shared_ptr<ir::DexFile> dex_ir) {
   printf("\nAvailable experiments:\n");
   printf("-------------------------\n");
   for (auto& e : experiments_registry) {
     printf("  %s\n", e.first.c_str());
   }
   printf("-------------------------\n\n");
 }

 // Driver for running experiments
 void Run(const char* experiment, std::shared_ptr<ir::DexFile> dex_ir) {
   auto it = experiments_registry.find(experiment);
   if (it == experiments_registry.end()) {
     printf("\nUnknown experiment '%s'\n", experiment);
     ListExperiments(dex_ir);
     exit(1);
   }

   // running the experiment entry point
   (*it->second)(dex_ir);
 }

 }  // namespace experimental
	/*
	* Copyright (C) 2017 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "experimental.h"
	#include "slicer/code_ir.h"
	#include "slicer/control_flow_graph.h"
	#include "slicer/dex_ir.h"
	#include "slicer/dex_ir_builder.h"
	#include "slicer/instrumentation.h"

	#include <string.h>
	#include <map>
	#include <memory>
	#include <vector>

	namespace experimental {

	// Rewrites every method through raising to code IR -> back to bytecode
	// (also stress the CFG creation)
	void FullRewrite(std::shared_ptr<ir::DexFile> dex_ir) {
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code != nullptr) {
	lir::CodeIr code_ir(ir_method.get(), dex_ir);
	lir::ControlFlowGraph cfg_compact(&code_ir, false);
	lir::ControlFlowGraph cfg_verbose(&code_ir, true);
	code_ir.Assemble();
	}
	}
	}

	// For every method body in the .dex image, replace invoke-virtual[/range]
	// instances with a invoke-static[/range] to a fictitious Tracer.WrapInvoke(<args...>)
	// WrapInvoke() is a static method which takes the same arguments as the
	// original method plus an explicit "this" argument, and returns the same
	// type as the original method.
	void StressWrapInvoke(std::shared_ptr<ir::DexFile> dex_ir) {
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code == nullptr) {
	continue;
	}

	lir::CodeIr code_ir(ir_method.get(), dex_ir);
	ir::Builder builder(dex_ir);

	// search for invoke-virtual[/range] bytecodes
	//
	// NOTE: we may be removing the current bytecode
	// from the instructions list so we must use a
	// different iteration style (it++ is done before
	// handling *it, not after as in a normal iteration)
	//
	auto it = code_ir.instructions.begin();
	while (it != code_ir.instructions.end()) {
	auto instr = *it++;
	auto bytecode = dynamic_cast<lir::Bytecode*>(instr);
	if (bytecode == nullptr) {
	continue;
	}

	dex::Opcode new_call_opcode = dex::OP_NOP;
	switch (bytecode->opcode) {
	case dex::OP_INVOKE_VIRTUAL:
	new_call_opcode = dex::OP_INVOKE_STATIC;
	break;
	case dex::OP_INVOKE_VIRTUAL_RANGE:
	new_call_opcode = dex::OP_INVOKE_STATIC_RANGE;
	break;
	default:
	// skip instruction ...
	continue;
	}
	assert(new_call_opcode != dex::OP_NOP);

	auto orig_method = bytecode->CastOperand<lir::Method>(1)->ir_method;

	// construct the wrapper method declaration
	std::vector<ir::Type*> param_types;
	param_types.push_back(orig_method->parent);
	if (orig_method->prototype->param_types != nullptr) {
	const auto& orig_param_types = orig_method->prototype->param_types->types;
	param_types.insert(param_types.end(), orig_param_types.begin(), orig_param_types.end());
	}

	auto ir_proto = builder.GetProto(orig_method->prototype->return_type,
	builder.GetTypeList(param_types));

	auto ir_method_decl = builder.GetMethodDecl(builder.GetAsciiString("WrapInvoke"),
	ir_proto,
	builder.GetType("LTracer;"));

	auto wraper_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

	// new call bytecode
	auto new_call = code_ir.Alloc<lir::Bytecode>();
	new_call->opcode = new_call_opcode;
	new_call->operands.push_back(bytecode->operands[0]);
	new_call->operands.push_back(wraper_method);
	code_ir.instructions.InsertBefore(bytecode, new_call);

	// remove the old call bytecode
	//
	// NOTE: we can mutate the original bytecode directly
	// since the instructions can't have multiple references
	// in the code IR, but for testing purposes we'll do it
	// the hard way here
	//
	code_ir.instructions.Remove(bytecode);
	}

	code_ir.Assemble();
	}
	}

	// For every method in the .dex image, insert an "entry hook" call
	// to a fictitious method: Tracer.OnEntry(<args...>). OnEntry() has the
	// same argument types as the instrumented method plus an explicit
	// "this" for non-static methods. On entry to the instumented method
	// we'll call OnEntry() with the values of the incoming arguments.
	//
	// NOTE: the entry hook will forward all the incoming arguments
	// so we need to define an Tracer.OnEntry overload for every method
	// signature. This means that for very large .dex images, approaching
	// the 64k method limit, we might not be able to allocate new method declarations.
	// (which is ok, and a good test case, since this is a stress scenario)
	//
	void StressEntryHook(std::shared_ptr<ir::DexFile> dex_ir) {
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code == nullptr) {
	continue;
	}

	lir::CodeIr code_ir(ir_method.get(), dex_ir);
	ir::Builder builder(dex_ir);

	// 1. construct call target
	std::vector<ir::Type*> param_types;
	if ((ir_method->access_flags & dex::kAccStatic) == 0) {
	param_types.push_back(ir_method->decl->parent);
	}
	if (ir_method->decl->prototype->param_types != nullptr) {
	const auto& orig_param_types = ir_method->decl->prototype->param_types->types;
	param_types.insert(param_types.end(), orig_param_types.begin(), orig_param_types.end());
	}

	auto ir_proto = builder.GetProto(builder.GetType("V"),
	builder.GetTypeList(param_types));

	auto ir_method_decl = builder.GetMethodDecl(builder.GetAsciiString("OnEntry"),
	ir_proto,
	builder.GetType("LTracer;"));

	auto target_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

	// 2. argument registers
	auto regs = ir_method->code->registers;
	auto args_count = ir_method->code->ins_count;
	auto args = code_ir.Alloc<lir::VRegRange>(regs - args_count, args_count);

	// 3. call bytecode
	auto call = code_ir.Alloc<lir::Bytecode>();
	call->opcode = dex::OP_INVOKE_STATIC_RANGE;
	call->operands.push_back(args);
	call->operands.push_back(target_method);

	// 4. insert the hook before the first bytecode
	for (auto instr : code_ir.instructions) {
	auto bytecode = dynamic_cast<lir::Bytecode*>(instr);
	if (bytecode == nullptr) {
	continue;
	}
	code_ir.instructions.InsertBefore(bytecode, call);
	break;
	}

	code_ir.Assemble();
	}
	}

	// For every method in the .dex image, insert an "exit hook" call
	// to a fictitious method: Tracer.OnExit(<return value...>).
	// OnExit() is called right before returning from the instrumented
	// method (on the non-exceptional path) and it will be passed the return
	// value, if any. For non-void return types, the return value from OnExit()
	// will also be used as the return value of the instrumented method.
	void StressExitHook(std::shared_ptr<ir::DexFile> dex_ir) {
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code == nullptr) {
	continue;
	}

	lir::CodeIr code_ir(ir_method.get(), dex_ir);
	ir::Builder builder(dex_ir);

	// do we have a void-return method?
	bool return_void =
	::strcmp(ir_method->decl->prototype->return_type->descriptor->c_str(), "V") == 0;

	// 1. construct call target
	std::vector<ir::Type*> param_types;
	if (!return_void) {
	param_types.push_back(ir_method->decl->prototype->return_type);
	}

	auto ir_proto = builder.GetProto(ir_method->decl->prototype->return_type,
	builder.GetTypeList(param_types));

	auto ir_method_decl = builder.GetMethodDecl(builder.GetAsciiString("OnExit"),
	ir_proto,
	builder.GetType("LTracer;"));

	auto target_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

	// 2. find and instrument the return instructions
	for (auto instr : code_ir.instructions) {
	auto bytecode = dynamic_cast<lir::Bytecode*>(instr);
	if (bytecode == nullptr) {
	continue;
	}

	dex::Opcode move_result_opcode = dex::OP_NOP;
	dex::u4 reg = 0;
	int reg_count = 0;

	switch (bytecode->opcode) {
	case dex::OP_RETURN_VOID:
	SLICER_CHECK(return_void);
	break;
	case dex::OP_RETURN:
	SLICER_CHECK(!return_void);
	move_result_opcode = dex::OP_MOVE_RESULT;
	reg = bytecode->CastOperand<lir::VReg>(0)->reg;
	reg_count = 1;
	break;
	case dex::OP_RETURN_OBJECT:
	SLICER_CHECK(!return_void);
	move_result_opcode = dex::OP_MOVE_RESULT_OBJECT;
	reg = bytecode->CastOperand<lir::VReg>(0)->reg;
	reg_count = 1;
	break;
	case dex::OP_RETURN_WIDE:
	SLICER_CHECK(!return_void);
	move_result_opcode = dex::OP_MOVE_RESULT_WIDE;
	reg = bytecode->CastOperand<lir::VRegPair>(0)->base_reg;
	reg_count = 2;
	break;
	default:
	// skip the bytecode...
	continue;
	}

	// the call bytecode
	auto args = code_ir.Alloc<lir::VRegRange>(reg, reg_count);
	auto call = code_ir.Alloc<lir::Bytecode>();
	call->opcode = dex::OP_INVOKE_STATIC_RANGE;
	call->operands.push_back(args);
	call->operands.push_back(target_method);
	code_ir.instructions.InsertBefore(bytecode, call);

	// move result back to the right register
	//
	// NOTE: we're reusing the original return's operand,
	// which is valid and more efficient than allocating
	// a new LIR node, but it's also fragile: we need to be
	// very careful about mutating shared nodes.
	//
	if (move_result_opcode != dex::OP_NOP) {
	auto move_result = code_ir.Alloc<lir::Bytecode>();
	move_result->opcode = move_result_opcode;
	move_result->operands.push_back(bytecode->operands[0]);
	code_ir.instructions.InsertBefore(bytecode, move_result);
	}
	}

	code_ir.Assemble();
	}
	}

	// Test slicer::MethodInstrumenter
	void TestMethodInstrumenter(std::shared_ptr<ir::DexFile> dex_ir) {
	slicer::MethodInstrumenter mi(dex_ir);
	mi.AddTransformation<slicer::EntryHook>(ir::MethodId("LTracer;", "onFooEntry"), true);
	mi.AddTransformation<slicer::EntryHook>(ir::MethodId("LTracer;", "onFooEntry"), false);
	mi.AddTransformation<slicer::ExitHook>(ir::MethodId("LTracer;", "onFooExit"));
	mi.AddTransformation<slicer::DetourVirtualInvoke>(
	ir::MethodId("LBase;", "foo", "(ILjava/lang/String;)I"),
	ir::MethodId("LTracer;", "wrapFoo"));
	mi.AddTransformation<slicer::DetourInterfaceInvoke>(
	ir::MethodId("LIBase;", "bar", "(Ljava/lang/String;)V"),
	ir::MethodId("LTracer;", "wrapBar"));

	auto method1 = ir::MethodId("LTarget;", "foo", "(ILjava/lang/String;)I");
	SLICER_CHECK(mi.InstrumentMethod(method1));

	auto method2 = ir::MethodId("LTarget;", "foo", "(I[[Ljava/lang/String;)Ljava/lang/Integer;");
	SLICER_CHECK(mi.InstrumentMethod(method2));
	}

	// Stress scratch register allocation
	void StressScratchRegs(std::shared_ptr<ir::DexFile> dex_ir) {
	slicer::MethodInstrumenter mi(dex_ir);

	// queue multiple allocations to stress corner cases (various counts and alignments)
	auto t1 = mi.AddTransformation<slicer::AllocateScratchRegs>(1, false);
	auto t2 = mi.AddTransformation<slicer::AllocateScratchRegs>(1, false);
	auto t3 = mi.AddTransformation<slicer::AllocateScratchRegs>(1);
	auto t4 = mi.AddTransformation<slicer::AllocateScratchRegs>(20);

	// apply the transformations to every single method
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code != nullptr) {
	SLICER_CHECK(mi.InstrumentMethod(ir_method.get()));
	SLICER_CHECK(t1->ScratchRegs().size() == 1);
	SLICER_CHECK(t2->ScratchRegs().size() == 1);
	SLICER_CHECK(t3->ScratchRegs().size() == 1);
	SLICER_CHECK(t4->ScratchRegs().size() == 20);
	}
	}
	}

	// Sample code coverage instrumentation: on the entry of every
	// basic block, inject a call to a tracing method:
	//
	// CodeCoverage.TraceBasicBlock(block_id)
	//
	void CodeCoverage(std::shared_ptr<ir::DexFile> dex_ir) {
	ir::Builder builder(dex_ir);
	slicer::AllocateScratchRegs alloc_regs(1);
	int basic_block_id = 1;

	constexpr const char* kTracerClass = "LCodeCoverage;";

	// create the tracing method declaration
	std::vector<ir::Type*> param_types { builder.GetType("I") };
	auto ir_proto =
	builder.GetProto(builder.GetType("V"),
	builder.GetTypeList(param_types));
	auto ir_method_decl =
	builder.GetMethodDecl(builder.GetAsciiString("TraceBasicBlock"),
	ir_proto,
	builder.GetType(kTracerClass));

	// instrument every method (except for the tracer class methods)
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code == nullptr) {
	continue;
	}

	// don't instrument the methods of the tracer class
	if (std::strcmp(ir_method->decl->parent->descriptor->c_str(), kTracerClass) == 0) {
	continue;
	}

	lir::CodeIr code_ir(ir_method.get(), dex_ir);
	lir::ControlFlowGraph cfg(&code_ir, true);

	// allocate a scratch register
	//
	// NOTE: we're assuming this does not change the CFG!
	// (this is the case here, but transformations which
	// alter the basic blocks boundaries or the code flow
	// would invalidate existing CFGs)
	//
	alloc_regs.Apply(&code_ir);
	dex::u4 scratch_reg = *alloc_regs.ScratchRegs().begin();

	// TODO: handle very "high" registers
	if (scratch_reg > 0xff) {
	printf("WARNING: can't instrument method %s.%s%s\n",
	ir_method->decl->parent->Decl().c_str(),
	ir_method->decl->name->c_str(),
	ir_method->decl->prototype->Signature().c_str());
	continue;
	}

	auto tracing_method = code_ir.Alloc<lir::Method>(ir_method_decl, ir_method_decl->orig_index);

	// instrument each basic block entry point
	for (const auto& block : cfg.basic_blocks) {
	// generate the map of basic blocks
	printf("%8u: mi=%u s=%u e=%u\n",
	static_cast<dex::u4>(basic_block_id),
	ir_method->decl->orig_index,
	block.region.first->offset,
	block.region.last->offset);

	// find first bytecode in the basic block
	lir::Instruction* trace_point = nullptr;
	for (auto instr = block.region.first; instr != nullptr; instr = instr->next) {
	trace_point = dynamic_cast<lir::Bytecode*>(instr);
	if (trace_point != nullptr \|\| instr == block.region.last) {
	break;
	}
	}
	SLICER_CHECK(trace_point != nullptr);

	// special case: don't separate 'move-result-<kind>' from the preceding invoke
	auto opcode = static_cast<lir::Bytecode*>(trace_point)->opcode;
	if (opcode == dex::OP_MOVE_RESULT \|\|
	opcode == dex::OP_MOVE_RESULT_WIDE \|\|
	opcode == dex::OP_MOVE_RESULT_OBJECT) {
	trace_point = trace_point->next;
	}

	// arg_reg = block_id
	auto load_block_id = code_ir.Alloc<lir::Bytecode>();
	load_block_id->opcode = dex::OP_CONST;
	load_block_id->operands.push_back(code_ir.Alloc<lir::VReg>(scratch_reg));
	load_block_id->operands.push_back(code_ir.Alloc<lir::Const32>(basic_block_id));
	code_ir.instructions.InsertBefore(trace_point, load_block_id);

	// call the tracing method
	auto trace_call = code_ir.Alloc<lir::Bytecode>();
	trace_call->opcode = dex::OP_INVOKE_STATIC_RANGE;
	trace_call->operands.push_back(code_ir.Alloc<lir::VRegRange>(scratch_reg, 1));
	trace_call->operands.push_back(tracing_method);
	code_ir.instructions.InsertBefore(trace_point, trace_call);

	++basic_block_id;
	}

	code_ir.Assemble();
	}
	}

	// Stress the roundtrip: EncodedMethod -> MethodId -> FindMethod -> EncodedMethod
	// NOTE: until we start indexing methods this test is slow on debug builds + large .dex images
	void StressFindMethod(std::shared_ptr<ir::DexFile> dex_ir) {
	ir::Builder builder(dex_ir);
	int method_count = 0;
	for (auto& ir_method : dex_ir->encoded_methods) {
	auto decl = ir_method->decl;
	auto signature = decl->prototype->Signature();
	auto class_descriptor = decl->parent->descriptor;
	ir::MethodId method_id(class_descriptor->c_str(), decl->name->c_str(), signature.c_str());
	SLICER_CHECK(builder.FindMethod(method_id) == ir_method.get());
	++method_count;
	}
	printf("Everything looks fine, found %d methods.\n", method_count);
	}

	static void PrintHistogram(const std::map<int, int> histogram, const char* name) {
	constexpr int kHistogramWidth = 100;
	int max_count = 0;
	for (const auto& kv : histogram) {
	max_count = std::max(max_count, kv.second);
	}
	printf("\nHistogram: %s [max_count=%d]\n\n", name, max_count);
	for (const auto& kv : histogram) {
	printf("%6d [ %3d ] ", kv.second, kv.first);
	int hist_len = static_cast<int>(static_cast<double>(kv.second) / max_count * kHistogramWidth);
	for (int i = 0; i <= hist_len; ++i) {
	printf("*");
	}
	printf("\n");
	}
	}

	// Builds a histogram of registers count per method
	void RegsHistogram(std::shared_ptr<ir::DexFile> dex_ir) {
	std::map<int, int> regs_histogram;
	std::map<int, int> param_histogram;
	std::map<int, int> extra_histogram;
	for (auto& ir_method : dex_ir->encoded_methods) {
	if (ir_method->code != nullptr) {
	const int regs = ir_method->code->registers;
	const int ins = ir_method->code->ins_count;
	SLICER_CHECK(regs >= ins);
	regs_histogram[regs]++;
	param_histogram[ins]++;
	extra_histogram[regs - ins]++;
	}
	}
	PrintHistogram(regs_histogram, "Method registers");
	PrintHistogram(param_histogram, "Method parameter registers");
	PrintHistogram(regs_histogram, "Method extra registers (total - parameters)");
	}

	void ListExperiments(std::shared_ptr<ir::DexFile> dex_ir);

	using Experiment = void (*)(std::shared_ptr<ir::DexFile>);

	// the registry of available experiments
	std::map<std::string, Experiment> experiments_registry = {
	{ "list_experiments", &ListExperiments },
	{ "full_rewrite", &FullRewrite },
	{ "stress_entry_hook", &StressEntryHook },
	{ "stress_exit_hook", &StressExitHook },
	{ "stress_wrap_invoke", &StressWrapInvoke },
	{ "test_method_instrumenter", &TestMethodInstrumenter },
	{ "stress_find_method", &StressFindMethod },
	{ "stress_scratch_regs", &StressScratchRegs },
	{ "regs_histogram", &RegsHistogram },
	{ "code_coverage", &CodeCoverage },
	};

	// Lists all the registered experiments
	void ListExperiments(std::shared_ptr<ir::DexFile> dex_ir) {
	printf("\nAvailable experiments:\n");
	printf("-------------------------\n");
	for (auto& e : experiments_registry) {
	printf(" %s\n", e.first.c_str());
	}
	printf("-------------------------\n\n");
	}

	// Driver for running experiments
	void Run(const char* experiment, std::shared_ptr<ir::DexFile> dex_ir) {
	auto it = experiments_registry.find(experiment);
	if (it == experiments_registry.end()) {
	printf("\nUnknown experiment '%s'\n", experiment);
	ListExperiments(dex_ir);
	exit(1);
	}

	// running the experiment entry point
	(*it->second)(dex_ir);
	}

	} // namespace experimental