1// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_BACKEND_IL_TEST_HELPER_H_
6#define RUNTIME_VM_COMPILER_BACKEND_IL_TEST_HELPER_H_
7
8#include <utility>
9#include <vector>
10
11#include "include/dart_api.h"
12
13#include "platform/allocation.h"
14#include "vm/compiler/backend/flow_graph.h"
15#include "vm/compiler/backend/il.h"
16#include "vm/compiler/compiler_pass.h"
17#include "vm/compiler/compiler_state.h"
18#include "vm/compiler/jit/compiler.h"
19#include "vm/unit_test.h"
20
21// The helpers in this file make it easier to write C++ unit tests which assert
22// that Dart code gets turned into certain IR.
23//
24// Here is an example on how to use it:
25//
26// ISOLATE_UNIT_TEST_CASE(MyIRTest) {
27// const char* script = R"(
28// void foo() { ... }
29// void main() { foo(); }
30// )";
31//
32// // Load the script and exercise the code once.
33// const auto& lib = Library::Handle(LoadTestScript(script);
34//
35// // Cause the code to be exercised once (to populate ICData).
36// Invoke(lib, "main");
37//
38// // Look up the function.
39// const auto& function = Function::Handle(GetFunction(lib, "foo"));
40//
41// // Run the JIT compilation pipeline with two passes.
42// TestPipeline pipeline(function);
43// FlowGraph* graph = pipeline.RunJITPasses("ComputeSSA,TypePropagation");
44//
45// ...
46// }
47//
48namespace dart {
49
50class FlowGraph;
51class Function;
52class Library;
53
54LibraryPtr LoadTestScript(const char* script,
55 Dart_NativeEntryResolver resolver = nullptr,
56 const char* lib_uri = RESOLVED_USER_TEST_URI);
57
58FunctionPtr GetFunction(const Library& lib, const char* name);
59ClassPtr GetClass(const Library& lib, const char* name);
60TypeParameterPtr GetClassTypeParameter(const Class& klass, const char* name);
61TypeParameterPtr GetFunctionTypeParameter(const Function& fun,
62 const char* name);
63
64ObjectPtr Invoke(const Library& lib, const char* name);
65
66class TestPipeline : public ValueObject {
67 public:
68 explicit TestPipeline(const Function& function,
69 CompilerPass::PipelineMode mode)
70 : function_(function),
71 thread_(Thread::Current()),
72 compiler_state_(thread_,
73 mode == CompilerPass::PipelineMode::kAOT,
74 CompilerState::ShouldTrace(function)),
75 mode_(mode) {}
76 ~TestPipeline() { delete pass_state_; }
77
78 // As a side-effect this will populate
79 // - [ic_data_array_]
80 // - [parsed_function_]
81 // - [pass_state_]
82 // - [flow_graph_]
83 FlowGraph* RunPasses(std::initializer_list<CompilerPass::Id> passes);
84
85 void CompileGraphAndAttachFunction();
86
87 private:
88 const Function& function_;
89 Thread* thread_;
90 CompilerState compiler_state_;
91 CompilerPass::PipelineMode mode_;
92 ZoneGrowableArray<const ICData*>* ic_data_array_ = nullptr;
93 ParsedFunction* parsed_function_ = nullptr;
94 CompilerPassState* pass_state_ = nullptr;
95 FlowGraph* flow_graph_ = nullptr;
96};
97
98// Match opcodes used for [ILMatcher], see below.
99enum MatchOpCode {
100// Emit a match and match-and-move code for every instruction.
101#define DEFINE_MATCH_OPCODES(Instruction, _) \
102 kMatch##Instruction, kMatchAndMove##Instruction, \
103 kMatchAndMoveOptional##Instruction,
104 FOR_EACH_INSTRUCTION(DEFINE_MATCH_OPCODES)
105#undef DEFINE_MATCH_OPCODES
106
107 // Matches a branch and moves left.
108 kMatchAndMoveBranchTrue,
109
110 // Matches a branch and moves right.
111 kMatchAndMoveBranchFalse,
112
113 // Is ignored.
114 kNop,
115
116 // Moves forward across any instruction.
117 kMoveAny,
118
119 // Moves over all parallel moves.
120 kMoveParallelMoves,
121
122 // Moves forward until the next match code matches.
123 kMoveGlob,
124
125 // Invalid match opcode used as default [insert_before] argument to TryMatch
126 // to signal that no insertions should occur.
127 kInvalidMatchOpCode,
128};
129
130// Match codes used for [ILMatcher], see below.
131class MatchCode {
132 public:
133 MatchCode(MatchOpCode opcode) // NOLINT
134 : opcode_(opcode), capture_(nullptr) {}
135
136 MatchCode(MatchOpCode opcode, Instruction** capture)
137 : opcode_(opcode), capture_(capture) {}
138
139#define DEFINE_TYPED_CONSTRUCTOR(Type, ignored) \
140 MatchCode(MatchOpCode opcode, Type##Instr** capture) \
141 : opcode_(opcode), capture_(reinterpret_cast<Instruction**>(capture)) { \
142 RELEASE_ASSERT(opcode == kMatch##Type || opcode == kMatchAndMove##Type); \
143 }
144 FOR_EACH_INSTRUCTION(DEFINE_TYPED_CONSTRUCTOR)
145#undef DEFINE_TYPED_CONSTRUCTOR
146
147 MatchOpCode opcode() { return opcode_; }
148
149 private:
150 friend class ILMatcher;
151
152 MatchOpCode opcode_;
153 Instruction** capture_;
154};
155
156enum class ParallelMovesHandling {
157 // Matcher doesn't do anything special with ParallelMove instructions.
158 kDefault,
159 // All ParallelMove instructions are skipped.
160 // This mode is useful when matching a flow graph after the whole
161 // compiler pipeline, as it may have ParallelMove instructions
162 // at arbitrary architecture-dependent places.
163 kSkip,
164};
165
166// Used for matching a sequence of IL instructions including capturing support.
167//
168// Example:
169//
170// TargetEntryInstr* entry = ....;
171// BranchInstr* branch = nullptr;
172//
173// ILMatcher matcher(flow_graph, entry);
174// if (matcher.TryMatch({ kMoveGlob, {kMatchBranch, &branch}, })) {
175// EXPECT(branch->operation_cid() == kMintCid);
176// ...
177// }
178//
179// This match will start at [entry], follow any number instructions (including
180// [GotoInstr]s until a [BranchInstr] is found).
181//
182// If the match was successful, this returns `true` and updates the current
183// value for the cursor.
184class ILMatcher : public ValueObject {
185 public:
186 ILMatcher(FlowGraph* flow_graph,
187 Instruction* cursor,
188 bool trace = true,
189 ParallelMovesHandling parallel_moves_handling =
190 ParallelMovesHandling::kDefault)
191 : flow_graph_(flow_graph),
192 cursor_(cursor),
193 parallel_moves_handling_(parallel_moves_handling),
194 // clang-format off
195#if !defined(PRODUCT)
196 trace_(trace) {}
197#else
198 trace_(false) {}
199#endif
200 // clang-format on
201
202 Instruction* value() { return cursor_; }
203
204 // From the current [value] according to match_codes.
205 //
206 // Returns `true` if the match was successful and cursor has been updated,
207 // otherwise returns `false`.
208 //
209 // If [insert_before] is a valid match opcode, then it will be inserted
210 // before each MatchCode in [match_codes] prior to matching.
211 bool TryMatch(std::initializer_list<MatchCode> match_codes,
212 MatchOpCode insert_before = kInvalidMatchOpCode);
213
214 private:
215 Instruction* MatchInternal(std::vector<MatchCode> match_codes,
216 size_t i,
217 Instruction* cursor);
218
219 const char* MatchOpCodeToCString(MatchOpCode code);
220
221 FlowGraph* flow_graph_;
222 Instruction* cursor_;
223 ParallelMovesHandling parallel_moves_handling_;
224 bool trace_;
225};
226
227#if !defined(PRODUCT)
228#define ENTITY_TOCSTRING(v) ((v)->ToCString())
229#else
230#define ENTITY_TOCSTRING(v) "<?>"
231#endif
232
233// Helper to check various IL and object properties and informative error
234// messages if check fails. [entity] should be a pointer to a value.
235// [property] should be an expression which can refer to [entity] using
236// variable named [it].
237// [entity] is expected to have a ToCString() method in non-PRODUCT builds.
238#define EXPECT_PROPERTY(entity, property) \
239 do { \
240 auto& it = *entity; \
241 if (!(property)) { \
242 dart::Expect(__FILE__, __LINE__) \
243 .Fail("expected " #property " for " #entity " which is %s.\n", \
244 ENTITY_TOCSTRING(entity)); \
245 } \
246 } while (0)
247
248class FlowGraphBuilderHelper {
249 public:
250 FlowGraphBuilderHelper()
251 : state_(CompilerState::Current()),
252 flow_graph_(MakeDummyGraph(Thread::Current())) {
253 flow_graph_.CreateCommonConstants();
254 }
255
256 TargetEntryInstr* TargetEntry(intptr_t try_index = kInvalidTryIndex) const {
257 return new TargetEntryInstr(flow_graph_.allocate_block_id(), try_index,
258 state_.GetNextDeoptId());
259 }
260
261 JoinEntryInstr* JoinEntry(intptr_t try_index = kInvalidTryIndex) const {
262 return new JoinEntryInstr(flow_graph_.allocate_block_id(), try_index,
263 state_.GetNextDeoptId());
264 }
265
266 ConstantInstr* IntConstant(int64_t value) const {
267 return flow_graph_.GetConstant(
268 Integer::Handle(Integer::NewCanonical(value)));
269 }
270
271 ConstantInstr* DoubleConstant(double value) {
272 return flow_graph_.GetConstant(Double::Handle(Double::NewCanonical(value)));
273 }
274
275 static Definition* const kPhiSelfReference;
276
277 PhiInstr* Phi(JoinEntryInstr* join,
278 std::initializer_list<std::pair<BlockEntryInstr*, Definition*>>
279 incoming) {
280 auto phi = new PhiInstr(join, incoming.size());
281 for (size_t i = 0; i < incoming.size(); i++) {
282 auto input = new Value(flow_graph_.constant_dead());
283 phi->SetInputAt(i, input);
284 input->definition()->AddInputUse(input);
285 }
286 for (auto pair : incoming) {
287 pending_phis_.Add({phi, pair.first,
288 pair.second == kPhiSelfReference ? phi : pair.second});
289 }
290 return phi;
291 }
292
293 void FinishGraph() {
294 flow_graph_.DiscoverBlocks();
295 GrowableArray<BitVector*> dominance_frontier;
296 flow_graph_.ComputeDominators(&dominance_frontier);
297
298 for (auto& pending : pending_phis_) {
299 auto join = pending.phi->block();
300 EXPECT(pending.phi->InputCount() == join->PredecessorCount());
301 auto pred_index = join->IndexOfPredecessor(pending.pred);
302 EXPECT(pred_index != -1);
303 pending.phi->InputAt(pred_index)->BindTo(pending.defn);
304 }
305 }
306
307 FlowGraph* flow_graph() { return &flow_graph_; }
308
309 private:
310 static FlowGraph& MakeDummyGraph(Thread* thread) {
311 const Function& func = Function::ZoneHandle(Function::New(
312 String::Handle(Symbols::New(thread, "dummy")),
313 FunctionLayout::kRegularFunction,
314 /*is_static=*/true,
315 /*is_const=*/false,
316 /*is_abstract=*/false,
317 /*is_external=*/false,
318 /*is_native=*/true,
319 Class::Handle(thread->isolate()->object_store()->object_class()),
320 TokenPosition::kNoSource));
321
322 Zone* zone = thread->zone();
323 ParsedFunction* parsed_function = new (zone) ParsedFunction(thread, func);
324
325 parsed_function->set_scope(new LocalScope(nullptr, 0, 0));
326
327 auto graph_entry =
328 new GraphEntryInstr(*parsed_function, Compiler::kNoOSRDeoptId);
329
330 const intptr_t block_id = 1; // 0 is GraphEntry.
331 graph_entry->set_normal_entry(
332 new FunctionEntryInstr(graph_entry, block_id, kInvalidTryIndex,
333 CompilerState::Current().GetNextDeoptId()));
334 return *new FlowGraph(*parsed_function, graph_entry, block_id,
335 PrologueInfo{-1, -1});
336 }
337
338 CompilerState& state_;
339 FlowGraph& flow_graph_;
340
341 struct PendingPhiInput {
342 PhiInstr* phi;
343 BlockEntryInstr* pred;
344 Definition* defn;
345 };
346 GrowableArray<PendingPhiInput> pending_phis_;
347};
348
349} // namespace dart
350
351#endif // RUNTIME_VM_COMPILER_BACKEND_IL_TEST_HELPER_H_
352