1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/compiler/backend/code-generator.h"
6 #include "src/compiler/backend/instruction.h"
7 #include "src/compiler/common-operator.h"
8 #include "src/compiler/graph.h"
9 #include "src/compiler/linkage.h"
10 #include "src/compiler/machine-operator.h"
11 #include "src/compiler/node.h"
12 #include "src/compiler/operator.h"
13 #include "src/compiler/schedule.h"
14 #include "src/compiler/scheduler.h"
15 #include "src/objects/objects-inl.h"
16 #include "test/cctest/cctest.h"
17 
18 namespace v8 {
19 namespace internal {
20 namespace compiler {
21 
22 using TestInstr = v8::internal::compiler::Instruction;
23 using TestInstrSeq = v8::internal::compiler::InstructionSequence;
24 
25 // A testing helper for the register code abstraction.
26 class InstructionTester : public HandleAndZoneScope {
27  public:  // We're all friends here.
InstructionTester()28   InstructionTester()
29       : HandleAndZoneScope(kCompressGraphZone),
30         graph(zone()),
31         schedule(zone()),
32         common(zone()),
33         machine(zone()),
34         code(nullptr) {}
35 
36   Graph graph;
37   Schedule schedule;
38   CommonOperatorBuilder common;
39   MachineOperatorBuilder machine;
40   TestInstrSeq* code;
41 
zone()42   Zone* zone() { return main_zone(); }
43 
allocCode()44   void allocCode() {
45     if (schedule.rpo_order()->size() == 0) {
46       // Compute the RPO order.
47       Scheduler::ComputeSpecialRPO(main_zone(), &schedule);
48       CHECK_NE(0u, schedule.rpo_order()->size());
49     }
50     InstructionBlocks* instruction_blocks =
51         TestInstrSeq::InstructionBlocksFor(main_zone(), &schedule);
52     code = main_zone()->New<TestInstrSeq>(main_isolate(), main_zone(),
53                                           instruction_blocks);
54   }
55 
Int32Constant(int32_t val)56   Node* Int32Constant(int32_t val) {
57     Node* node = graph.NewNode(common.Int32Constant(val));
58     schedule.AddNode(schedule.start(), node);
59     return node;
60   }
61 
Float64Constant(double val)62   Node* Float64Constant(double val) {
63     Node* node = graph.NewNode(common.Float64Constant(val));
64     schedule.AddNode(schedule.start(), node);
65     return node;
66   }
67 
Parameter(int32_t which)68   Node* Parameter(int32_t which) {
69     Node* node = graph.NewNode(common.Parameter(which));
70     schedule.AddNode(schedule.start(), node);
71     return node;
72   }
73 
NewNode(BasicBlock * block)74   Node* NewNode(BasicBlock* block) {
75     Node* node = graph.NewNode(common.Int32Constant(111));
76     schedule.AddNode(block, node);
77     return node;
78   }
79 
NewInstr()80   int NewInstr() {
81     InstructionCode opcode = static_cast<InstructionCode>(110);
82     TestInstr* instr = TestInstr::New(zone(), opcode);
83     return code->AddInstruction(instr);
84   }
85 
NewNop()86   int NewNop() {
87     TestInstr* instr = TestInstr::New(zone(), kArchNop);
88     return code->AddInstruction(instr);
89   }
90 
Unallocated(int vreg)91   UnallocatedOperand Unallocated(int vreg) {
92     return UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT, vreg);
93   }
94 
RpoFor(BasicBlock * block)95   RpoNumber RpoFor(BasicBlock* block) {
96     return RpoNumber::FromInt(block->rpo_number());
97   }
98 
BlockAt(BasicBlock * block)99   InstructionBlock* BlockAt(BasicBlock* block) {
100     return code->InstructionBlockAt(RpoFor(block));
101   }
GetBasicBlock(int instruction_index)102   BasicBlock* GetBasicBlock(int instruction_index) {
103     const InstructionBlock* block =
104         code->GetInstructionBlock(instruction_index);
105     return schedule.rpo_order()->at(block->rpo_number().ToSize());
106   }
first_instruction_index(BasicBlock * block)107   int first_instruction_index(BasicBlock* block) {
108     return BlockAt(block)->first_instruction_index();
109   }
last_instruction_index(BasicBlock * block)110   int last_instruction_index(BasicBlock* block) {
111     return BlockAt(block)->last_instruction_index();
112   }
113 };
114 
115 
TEST(InstructionBasic)116 TEST(InstructionBasic) {
117   InstructionTester R;
118 
119   for (int i = 0; i < 10; i++) {
120     R.Int32Constant(i);  // Add some nodes to the graph.
121   }
122 
123   BasicBlock* last = R.schedule.start();
124   for (int i = 0; i < 5; i++) {
125     BasicBlock* block = R.schedule.NewBasicBlock();
126     R.schedule.AddGoto(last, block);
127     last = block;
128   }
129 
130   R.allocCode();
131 
132   BasicBlockVector* blocks = R.schedule.rpo_order();
133   CHECK_EQ(static_cast<int>(blocks->size()), R.code->InstructionBlockCount());
134 
135   for (auto block : *blocks) {
136     CHECK_EQ(block->rpo_number(), R.BlockAt(block)->rpo_number().ToInt());
137     CHECK(!block->loop_end());
138   }
139 }
140 
141 
TEST(InstructionGetBasicBlock)142 TEST(InstructionGetBasicBlock) {
143   InstructionTester R;
144 
145   BasicBlock* b0 = R.schedule.start();
146   BasicBlock* b1 = R.schedule.NewBasicBlock();
147   BasicBlock* b2 = R.schedule.NewBasicBlock();
148   BasicBlock* b3 = R.schedule.end();
149 
150   R.schedule.AddGoto(b0, b1);
151   R.schedule.AddGoto(b1, b2);
152   R.schedule.AddGoto(b2, b3);
153 
154   R.allocCode();
155 
156   R.code->StartBlock(R.RpoFor(b0));
157   int i0 = R.NewInstr();
158   int i1 = R.NewInstr();
159   R.code->EndBlock(R.RpoFor(b0));
160   R.code->StartBlock(R.RpoFor(b1));
161   int i2 = R.NewInstr();
162   int i3 = R.NewInstr();
163   int i4 = R.NewInstr();
164   int i5 = R.NewInstr();
165   R.code->EndBlock(R.RpoFor(b1));
166   R.code->StartBlock(R.RpoFor(b2));
167   int i6 = R.NewInstr();
168   int i7 = R.NewInstr();
169   int i8 = R.NewInstr();
170   R.code->EndBlock(R.RpoFor(b2));
171   R.code->StartBlock(R.RpoFor(b3));
172   R.NewNop();
173   R.code->EndBlock(R.RpoFor(b3));
174 
175   CHECK_EQ(b0, R.GetBasicBlock(i0));
176   CHECK_EQ(b0, R.GetBasicBlock(i1));
177 
178   CHECK_EQ(b1, R.GetBasicBlock(i2));
179   CHECK_EQ(b1, R.GetBasicBlock(i3));
180   CHECK_EQ(b1, R.GetBasicBlock(i4));
181   CHECK_EQ(b1, R.GetBasicBlock(i5));
182 
183   CHECK_EQ(b2, R.GetBasicBlock(i6));
184   CHECK_EQ(b2, R.GetBasicBlock(i7));
185   CHECK_EQ(b2, R.GetBasicBlock(i8));
186 
187   CHECK_EQ(b0, R.GetBasicBlock(R.first_instruction_index(b0)));
188   CHECK_EQ(b0, R.GetBasicBlock(R.last_instruction_index(b0)));
189 
190   CHECK_EQ(b1, R.GetBasicBlock(R.first_instruction_index(b1)));
191   CHECK_EQ(b1, R.GetBasicBlock(R.last_instruction_index(b1)));
192 
193   CHECK_EQ(b2, R.GetBasicBlock(R.first_instruction_index(b2)));
194   CHECK_EQ(b2, R.GetBasicBlock(R.last_instruction_index(b2)));
195 
196   CHECK_EQ(b3, R.GetBasicBlock(R.first_instruction_index(b3)));
197   CHECK_EQ(b3, R.GetBasicBlock(R.last_instruction_index(b3)));
198 }
199 
200 
TEST(InstructionIsGapAt)201 TEST(InstructionIsGapAt) {
202   InstructionTester R;
203 
204   BasicBlock* b0 = R.schedule.start();
205   R.schedule.AddReturn(b0, R.Int32Constant(1));
206 
207   R.allocCode();
208   TestInstr* i0 = TestInstr::New(R.zone(), 100);
209   TestInstr* g = TestInstr::New(R.zone(), 103);
210   R.code->StartBlock(R.RpoFor(b0));
211   R.code->AddInstruction(i0);
212   R.code->AddInstruction(g);
213   R.code->EndBlock(R.RpoFor(b0));
214 
215   CHECK_EQ(2, R.code->instructions().size());
216 }
217 
218 
TEST(InstructionIsGapAt2)219 TEST(InstructionIsGapAt2) {
220   InstructionTester R;
221 
222   BasicBlock* b0 = R.schedule.start();
223   BasicBlock* b1 = R.schedule.end();
224   R.schedule.AddGoto(b0, b1);
225   R.schedule.AddReturn(b1, R.Int32Constant(1));
226 
227   R.allocCode();
228   TestInstr* i0 = TestInstr::New(R.zone(), 100);
229   TestInstr* g = TestInstr::New(R.zone(), 103);
230   R.code->StartBlock(R.RpoFor(b0));
231   R.code->AddInstruction(i0);
232   R.code->AddInstruction(g);
233   R.code->EndBlock(R.RpoFor(b0));
234 
235   TestInstr* i1 = TestInstr::New(R.zone(), 102);
236   TestInstr* g1 = TestInstr::New(R.zone(), 104);
237   R.code->StartBlock(R.RpoFor(b1));
238   R.code->AddInstruction(i1);
239   R.code->AddInstruction(g1);
240   R.code->EndBlock(R.RpoFor(b1));
241 
242   CHECK_EQ(4, R.code->instructions().size());
243 }
244 
245 
TEST(InstructionAddGapMove)246 TEST(InstructionAddGapMove) {
247   InstructionTester R;
248 
249   BasicBlock* b0 = R.schedule.start();
250   R.schedule.AddReturn(b0, R.Int32Constant(1));
251 
252   R.allocCode();
253   TestInstr* i0 = TestInstr::New(R.zone(), 100);
254   TestInstr* g = TestInstr::New(R.zone(), 103);
255   R.code->StartBlock(R.RpoFor(b0));
256   R.code->AddInstruction(i0);
257   R.code->AddInstruction(g);
258   R.code->EndBlock(R.RpoFor(b0));
259 
260   CHECK_EQ(2, R.code->instructions().size());
261 
262   int index = 0;
263   for (auto instr : R.code->instructions()) {
264     UnallocatedOperand op1 = R.Unallocated(index++);
265     UnallocatedOperand op2 = R.Unallocated(index++);
266     instr->GetOrCreateParallelMove(TestInstr::START, R.zone())
267         ->AddMove(op1, op2);
268     ParallelMove* move = instr->GetParallelMove(TestInstr::START);
269     CHECK(move);
270     CHECK_EQ(1u, move->size());
271     MoveOperands* cur = move->at(0);
272     CHECK(op1.Equals(cur->source()));
273     CHECK(op2.Equals(cur->destination()));
274   }
275 }
276 
277 
TEST(InstructionOperands)278 TEST(InstructionOperands) {
279   v8::internal::AccountingAllocator allocator;
280   Zone zone(&allocator, ZONE_NAME);
281 
282   {
283     TestInstr* i = TestInstr::New(&zone, 101);
284     CHECK_EQ(0, static_cast<int>(i->OutputCount()));
285     CHECK_EQ(0, static_cast<int>(i->InputCount()));
286     CHECK_EQ(0, static_cast<int>(i->TempCount()));
287   }
288 
289   int vreg = 15;
290   InstructionOperand outputs[] = {
291       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
292       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
293       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
294       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg)};
295 
296   InstructionOperand inputs[] = {
297       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
298       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
299       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
300       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg)};
301 
302   InstructionOperand temps[] = {
303       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
304       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
305       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg),
306       UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg)};
307 
308   for (size_t i = 0; i < arraysize(outputs); i++) {
309     for (size_t j = 0; j < arraysize(inputs); j++) {
310       for (size_t k = 0; k < arraysize(temps); k++) {
311         TestInstr* m =
312             TestInstr::New(&zone, 101, i, outputs, j, inputs, k, temps);
313         CHECK(i == m->OutputCount());
314         CHECK(j == m->InputCount());
315         CHECK(k == m->TempCount());
316 
317         for (size_t z = 0; z < i; z++) {
318           CHECK(outputs[z].Equals(*m->OutputAt(z)));
319         }
320 
321         for (size_t z = 0; z < j; z++) {
322           CHECK(inputs[z].Equals(*m->InputAt(z)));
323         }
324 
325         for (size_t z = 0; z < k; z++) {
326           CHECK(temps[z].Equals(*m->TempAt(z)));
327         }
328       }
329     }
330   }
331 }
332 
333 }  // namespace compiler
334 }  // namespace internal
335 }  // namespace v8
336