1 : // Copyright 2013 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // This class implements the functions inlining transformation.
16 : //
17 : // Performing inline expansion on assembly is not an easy task. As the transform
18 : // runs after the standard compiler WPO, it may face custom calling convention
19 : // and strange stack manipulations. Thus, every expansion must be safe.
20 : //
21 : // The pattern based inlining is able to inline many common cases encounter with
22 : // common compilers. This inlining transformation avoids decomposing the block
23 : // which is much more efficient.
24 : // Example:
25 : // - push ebp
26 : // mov ebp, esp
27 : // pop ebp
28 : // ret
29 : //
30 : // The trivial body inlining is able to inline any trivial accessors.
31 : // Assumptions:
32 : // - No stack manipulations (except local push/pop).
33 : // - No branching instructions (except the last return or jump).
34 : // - No basic blocks reference, data block, jump-table, etc...
35 : // Example:
36 : // - xor eax, eax
37 : // ret
38 :
39 : #include "syzygy/optimize/transforms/inlining_transform.h"
40 :
41 : #include "syzygy/block_graph/basic_block.h"
42 : #include "syzygy/block_graph/basic_block_assembler.h"
43 : #include "syzygy/block_graph/basic_block_decomposer.h"
44 : #include "syzygy/block_graph/block_graph.h"
45 : // TODO(etienneb): liveness analysis internal should be hoisted to an
46 : // instructions helper namespace, and shared between analysis. It is quite
47 : // common to get the information on registers defined or used by an
48 : // instruction, or the memory operand read and written.
49 : #include "syzygy/block_graph/analysis/liveness_analysis_internal.h"
50 : #include "syzygy/optimize/transforms/peephole_transform.h"
51 :
52 : namespace optimize {
53 : namespace transforms {
54 :
55 : namespace {
56 :
57 : using block_graph::BasicBlock;
58 : using block_graph::BasicBlockAssembler;
59 : using block_graph::BasicBlockDecomposer;
60 : using block_graph::BasicBlockReference;
61 : using block_graph::BasicBlockSubGraph;
62 : using block_graph::BasicCodeBlock;
63 : using block_graph::BlockGraph;
64 : using block_graph::Displacement;
65 : using block_graph::Immediate;
66 : using block_graph::Instruction;
67 : using block_graph::Operand;
68 : using block_graph::Successor;
69 : using block_graph::analysis::LivenessAnalysis;
70 :
71 : typedef ApplicationProfile::BlockProfile BlockProfile;
72 : typedef Instruction::BasicBlockReferenceMap BasicBlockReferenceMap;
73 : typedef BasicBlockSubGraph::BBCollection BBCollection;
74 : typedef BasicBlock::Instructions Instructions;
75 : typedef BlockGraph::Offset Offset;
76 : typedef scoped_ptr<BasicBlockSubGraph> ScopedSubgraph;
77 :
78 : enum MatchKind {
79 : kInvalidMatch,
80 : kReturnMatch,
81 : kReturnConstantMatch,
82 : kDirectTrampolineMatch,
83 : kIndirectTrampolineMatch,
84 : };
85 :
86 : // Threshold in bytes to consider a block as a candidate for inlining. This size
87 : // must be big enough to don't miss good candidates, but small to avoid the
88 : // overhead of decomposition and simplification of huge block.
89 : const size_t kCodeSizeThreshold = 25;
90 :
91 : // Threshold in bytes to inline a callee in a hot block.
92 : const size_t kHotCodeSizeThreshold = 15;
93 :
94 : // Threshold in bytes to inline a callee in a cold block.
95 : const size_t kColdCodeSizeThreshold = 1;
96 :
97 : // A size huge enough to never be an inlining candidate.
98 : const size_t kHugeBlockSize = 0xFFFFFFFF;
99 :
100 : // These patterns are often produced by the MSVC compiler. They're common enough
101 : // that the inlining transformation matches them by pattern rather than
102 : // disassembling them.
103 :
104 : // ret
105 : const uint8 kEmptyBody1[] = { 0xC3 };
106 :
107 : // push %ebp
108 : // mov %ebp, %esp
109 : // pop %ebp
110 : // ret
111 : const uint8 kEmptyBody2[] = { 0x55, 0x8B, 0xEC, 0x5D, 0xC3 };
112 :
113 : // push %ebp
114 : // mov %ebp, %esp
115 : // mov %eax, [%ebp + 0x4]
116 : // pop %ebp
117 : // ret
118 : const uint8 kGetProgramCounter[] = {
119 : 0x55, 0x8B, 0xEC, 0x8B, 0x45, 0x04, 0x5D, 0xC3 };
120 :
121 : // Match a call instruction to a direct callee (i.e. no indirect calls).
122 E : bool MatchDirectCall(const Instruction& instr, BlockGraph::Block** callee) {
123 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block**>(NULL), callee);
124 :
125 : // Match a call instruction with one reference.
126 E : const _DInst& repr = instr.representation();
127 : if (!instr.IsCall() ||
128 : repr.ops[0].type != O_PC ||
129 E : instr.references().size() != 1) {
130 E : return false;
131 : }
132 :
133 : // The callee must be the beginning of a code block.
134 E : const BasicBlockReference& ref = instr.references().begin()->second;
135 E : BlockGraph::Block* block = ref.block();
136 : if (block == NULL ||
137 : ref.base() != 0 ||
138 : ref.offset() != 0 ||
139 E : block->type() != BlockGraph::CODE_BLOCK) {
140 E : return false;
141 : }
142 :
143 : // Returns the matched callee.
144 E : *callee = block;
145 E : return true;
146 E : }
147 :
148 : bool MatchRawBytes(BlockGraph::Block* callee,
149 : const uint8* bytes,
150 E : size_t length) {
151 : if (callee->size() != length ||
152 E : ::memcmp(callee->data(), bytes, length) != 0) {
153 E : return false;
154 : }
155 :
156 E : return true;
157 E : }
158 :
159 E : bool MatchGetProgramCounter(BlockGraph::Block* callee) {
160 E : size_t length = sizeof(kGetProgramCounter);
161 E : if (MatchRawBytes(callee, kGetProgramCounter, length))
162 i : return true;
163 :
164 E : return false;
165 E : }
166 :
167 E : bool MatchEmptyBody(BlockGraph::Block* callee) {
168 E : size_t length1 = sizeof(kEmptyBody1);
169 E : if (MatchRawBytes(callee, kEmptyBody1, length1))
170 E : return true;
171 :
172 E : size_t length2 = sizeof(kEmptyBody2);
173 E : if (MatchRawBytes(callee, kEmptyBody2, length2))
174 E : return true;
175 :
176 E : return false;
177 E : }
178 :
179 : // Match trivial body in a subgraph. A trivial body is a single basic block
180 : // without control flow, stack manipulation or other unsupported constructs.
181 : // @param subgraph The subgraph to try matching a trivial body.
182 : // @param kind On a match, receives the kind of match was found.
183 : // @param return_constant Receives the number of bytes to pop from the stack
184 : // after the body (when kind is kReturnConstantMatch).
185 : // @param reference Receives a reference to a target continuation (when kind is
186 : // kDirectTrampolineMatch or kIndirectTrampolineMatch).
187 : // @param body On success, receives the trivial body.
188 : // @returns true on success, false otherwise.
189 : bool MatchTrivialBody(const BasicBlockSubGraph& subgraph,
190 : MatchKind* kind,
191 : size_t* return_constant,
192 : BasicBlockReference* reference,
193 E : BasicCodeBlock** body) {
194 E : DCHECK_NE(reinterpret_cast<MatchKind*>(NULL), kind);
195 E : DCHECK_NE(reinterpret_cast<size_t*>(NULL), return_constant);
196 E : DCHECK_NE(reinterpret_cast<BasicBlockReference*>(NULL), reference);
197 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock**>(NULL), body);
198 :
199 : // Assume no match.
200 E : *kind = kInvalidMatch;
201 :
202 : // Trivial body only has one code basic block, and one end block.
203 E : if (subgraph.basic_blocks().size() != 2)
204 i : return false;
205 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(*subgraph.basic_blocks().begin());
206 E : if (bb == NULL)
207 i : return false;
208 :
209 : // Current local stack depth.
210 E : size_t stack_depth = 0;
211 :
212 : // Iterates through each instruction.
213 E : Instructions::iterator inst_iter = bb->instructions().begin();
214 E : for (; inst_iter != bb->instructions().end(); ++inst_iter) {
215 E : const Instruction& instr = *inst_iter;
216 E : const _DInst& repr = instr.representation();
217 :
218 : // Do not allow any references to a basic block.
219 E : const BasicBlockReferenceMap& references = instr.references();
220 E : BasicBlockReferenceMap::const_iterator ref = references.begin();
221 E : for (; ref != references.end(); ++ref) {
222 : if (ref->second.referred_type() ==
223 E : BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK) {
224 i : return false;
225 : }
226 E : }
227 :
228 : // Return instruction is valid.
229 E : if (instr.IsReturn()) {
230 : // Match return with or without a constant.
231 E : if (repr.ops[0].type == O_NONE) {
232 E : *kind = kReturnMatch;
233 E : } else if (repr.ops[0].type == O_IMM) {
234 E : *kind = kReturnConstantMatch;
235 E : *return_constant = repr.imm.dword;
236 E : } else {
237 i : return false;
238 : }
239 :
240 : // Move to the next instruction and leave loop. This instruction must be
241 : // the last one in the basic block.
242 E : ++inst_iter;
243 E : break;
244 : }
245 :
246 : // Match an indirect jump from a global variable.
247 E : BasicBlockReference target_ref;
248 : if (instr.IsBranch() &&
249 : instr.references().size() == 1 &&
250 : instr.FindOperandReference(0, &target_ref) &&
251 : target_ref.block() != NULL &&
252 : repr.opcode == I_JMP &&
253 : repr.ops[0].type == O_DISP &&
254 : repr.ops[0].size == 32 &&
255 E : repr.ops[0].index == 0) {
256 : // Match displacement to a block.
257 E : *kind = kIndirectTrampolineMatch;
258 E : *reference = target_ref;
259 :
260 : // Move to the next instruction and leave loop. This instruction must be
261 : // the last one in the basic block.
262 E : ++inst_iter;
263 E : break;
264 : }
265 :
266 : // Avoid control flow instructions.
267 E : if (instr.IsControlFlow())
268 i : return false;
269 :
270 : // Avoid unsafe stack manipulation.
271 : if (repr.opcode == I_PUSH &&
272 : (repr.ops[0].type == O_IMM ||
273 : repr.ops[0].type == O_IMM1 ||
274 E : repr.ops[0].type == O_IMM2)) {
275 : // Pushing a constant is valid.
276 E : stack_depth += 4;
277 E : } else if (repr.opcode == I_PUSH &&
278 : repr.ops[0].type == O_REG &&
279 : repr.ops[0].index != R_EBP &&
280 E : repr.ops[0].index != R_ESP) {
281 : // Pushing a register is valid.
282 E : stack_depth += 4;
283 E : } else if (repr.opcode == I_POP &&
284 : repr.ops[0].type == O_REG &&
285 : repr.ops[0].index != R_EBP &&
286 : repr.ops[0].index != R_ESP &&
287 E : stack_depth >= 4) {
288 : // Popping a register is valid.
289 E : stack_depth -= 4;
290 E : } else {
291 E : LivenessAnalysis::State defs;
292 E : LivenessAnalysis::StateHelper::GetDefsOf(instr, &defs);
293 :
294 E : LivenessAnalysis::State uses;
295 E : LivenessAnalysis::StateHelper::GetUsesOf(instr, &uses);
296 :
297 : if (defs.IsLive(assm::esp) ||
298 : defs.IsLive(assm::ebp) ||
299 : uses.IsLive(assm::esp) ||
300 E : uses.IsLive(assm::ebp)) {
301 E : return false;
302 : }
303 : }
304 E : }
305 :
306 : // All instructions must have been checked.
307 E : if (inst_iter != bb->instructions().end())
308 i : return false;
309 :
310 E : if (*kind == kInvalidMatch) {
311 : // Try to match a tail-call to an other block.
312 : if (bb->successors().size() != 1 ||
313 E : bb->successors().front().condition() != Successor::kConditionTrue) {
314 E : return false;
315 : }
316 :
317 : // Must match a valid reference to a block.
318 E : const Successor& succ = bb->successors().front();
319 E : const BasicBlockReference& ref = succ.reference();
320 E : if (ref.block() == NULL)
321 E : return false;
322 :
323 : // Matched a direct trampoline.
324 E : *kind = kDirectTrampolineMatch;
325 E : *reference = ref;
326 E : } else {
327 : // The basic block must have a return (to remove the caller address on
328 : // stack) or be an indirect tail-call to an other block and must not have
329 : // successors.
330 E : if (!bb->successors().empty())
331 i : return false;
332 : }
333 :
334 : // Returns the matched body.
335 E : DCHECK_NE(kInvalidMatch, *kind);
336 E : *body = bb;
337 E : return true;
338 E : }
339 :
340 : // Replace block references to the current block by basic block references.
341 : // @param subgraph The caller subgraph.
342 : // @param instructions Instructions copied into the caller.
343 : bool RewriteLocalReferences(BasicBlockSubGraph* subgraph,
344 E : Instructions* instructions) {
345 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
346 : DCHECK_NE(reinterpret_cast<const BlockGraph::Block*>(NULL),
347 E : subgraph->original_block());
348 E : DCHECK_NE(reinterpret_cast<Instructions*>(NULL), instructions);
349 :
350 E : Instructions::iterator instr = instructions->begin();
351 E : for (; instr != instructions->end(); ++instr) {
352 E : const BasicBlockReferenceMap& references = instr->references();
353 E : BasicBlockReferenceMap::const_iterator ref = references.begin();
354 E : while (ref != references.end()) {
355 E : Offset offset = ref->first;
356 E : const BasicBlockReference& reference = ref->second;
357 :
358 : // Move to the next reference, the current one is updated below.
359 E : ++ref;
360 :
361 : if (reference.referred_type() !=
362 : BasicBlockReference::REFERRED_TYPE_BLOCK ||
363 E : reference.block() != subgraph->original_block()) {
364 E : continue;
365 : }
366 :
367 : // Find the basic block targeted by the reference.
368 E : BasicBlock* target = NULL;
369 E : BBCollection& basic_blocks = subgraph->basic_blocks();
370 E : BBCollection::iterator bb = basic_blocks.begin();
371 E : for (; bb != basic_blocks.end(); ++bb) {
372 E : if ((*bb)->offset() == reference.offset()) {
373 E : DCHECK_EQ(reinterpret_cast<BasicBlock*>(NULL), target);
374 E : target = *bb;
375 : }
376 E : }
377 :
378 E : DCHECK_NE(reinterpret_cast<BasicBlock*>(NULL), target);
379 :
380 : // Replace the current block reference with a basic block reference.
381 : instr->SetReference(
382 : offset,
383 : BasicBlockReference(reference.reference_type(),
384 : reference.size(),
385 E : target));
386 E : }
387 E : }
388 E : return true;
389 E : }
390 :
391 : // Copy the body of the callee at a call-site in the caller.
392 : // @param kind The kind of inlining to perform.
393 : // @param subgraph The caller subgraph.
394 : // @param return_constant The number of bytes to pop from the stack.
395 : // @param reference The reference to the continuation.
396 : // @param body The trivial body to be inlined.
397 : // @param target The place where to insert the callee body into the caller.
398 : // @param instructions The caller body that receives a copy of the callee body.
399 : // @returns true on success, false otherwise.
400 : bool InlineTrivialBody(MatchKind kind,
401 : BasicBlockSubGraph* subgraph,
402 : size_t return_constant,
403 : const BasicBlockReference& reference,
404 : const BasicCodeBlock* body,
405 : Instructions::iterator target,
406 E : Instructions* instructions) {
407 E : DCHECK_NE(reinterpret_cast<Instructions*>(NULL), instructions);
408 :
409 E : Instructions new_body;
410 :
411 : // Iterates through each instruction.
412 E : Instructions::const_iterator inst_iter = body->instructions().begin();
413 E : for (; inst_iter != body->instructions().end(); ++inst_iter) {
414 E : const Instruction& instr = *inst_iter;
415 E : const _DInst& repr = instr.representation();
416 :
417 E : if (instr.IsBranch()) {
418 : // Skip the indirect branch instruction.
419 E : DCHECK_EQ(kind, kIndirectTrampolineMatch);
420 E : } else if (instr.IsReturn()) {
421 : // Nothing to do here with return instruction (see below).
422 E : } else {
423 E : new_body.push_back(instr);
424 : }
425 E : }
426 :
427 : // Replacing the return or the tail-call instruction.
428 E : BasicBlockAssembler assembler(new_body.end(), &new_body);
429 E : switch (kind) {
430 : case kReturnMatch:
431 E : break;
432 : case kReturnConstantMatch:
433 : // Replace a 'ret 4' instruction by a 'lea %esp, [%esp + 0x4]'.
434 : // Instruction add cannot be used because flags must be preserved,
435 : assembler.lea(assm::esp,
436 E : Operand(assm::esp, Displacement(return_constant)));
437 E : break;
438 : case kDirectTrampolineMatch:
439 E : DCHECK(reference.IsValid());
440 : assembler.call(
441 E : Immediate(reference.block(), reference.offset(), reference.base()));
442 E : break;
443 : case kIndirectTrampolineMatch:
444 E : DCHECK(reference.IsValid());
445 : assembler.call(Operand(Displacement(reference.block(),
446 : reference.offset(),
447 E : reference.base())));
448 E : break;
449 : default:
450 i : NOTREACHED();
451 : }
452 :
453 : // Replace block references to the caller block by basic block references.
454 E : if (!RewriteLocalReferences(subgraph, &new_body))
455 i : return false;
456 :
457 : // Insert the inlined instructions at the call-site.
458 E : instructions->splice(target, new_body);
459 E : return true;
460 E : }
461 :
462 : // Decompose a block to a subgraph.
463 : bool DecomposeToBasicBlock(const BlockGraph::Block* block,
464 E : BasicBlockSubGraph* subgraph) {
465 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), block);
466 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
467 :
468 : // Decompose block to basic blocks.
469 E : BasicBlockDecomposer decomposer(block, subgraph);
470 E : if (!decomposer.Decompose())
471 i : return false;
472 :
473 E : return true;
474 E : }
475 :
476 : bool DecomposeCalleeBlock(const BlockGraph::Block* callee,
477 E : ScopedSubgraph* callee_subgraph) {
478 E : DCHECK_NE(reinterpret_cast<const BlockGraph::Block*>(NULL), callee);
479 E : DCHECK_NE(reinterpret_cast<ScopedSubgraph*>(NULL), callee_subgraph);
480 :
481 : // Create a new subgraph.
482 E : callee_subgraph->reset(new BasicBlockSubGraph());
483 :
484 : // Decompose it.
485 E : if (!DecomposeToBasicBlock(callee, callee_subgraph->get()))
486 i : return false;
487 :
488 : // Simplify the subgraph. There is no guarantee that the callee has been
489 : // simplified by the peephole transform. Running one pass should take
490 : // care of the most frequent patterns.
491 E : PeepholeTransform::SimplifySubgraph(callee_subgraph->get());
492 :
493 E : return true;
494 E : }
495 :
496 E : size_t EstimateSubgraphSize(BasicBlockSubGraph* subgraph) {
497 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
498 E : const size_t kMaxBranchSize = 5;
499 E : size_t size = 0;
500 E : BBCollection& basic_blocks = subgraph->basic_blocks();
501 E : BBCollection::iterator it = basic_blocks.begin();
502 E : for (; it != basic_blocks.end(); ++it) {
503 : // End blocks contribute nothing to the total size.
504 E : if ((*it)->type() == BasicBlock::BASIC_END_BLOCK)
505 E : continue;
506 :
507 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(*it);
508 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), bb);
509 E : BasicBlock::Instructions::iterator inst_iter = bb->instructions().begin();
510 :
511 : // Sum of instructions size.
512 E : for (; inst_iter != bb->instructions().end(); ++inst_iter)
513 E : size += inst_iter->size();
514 :
515 : // Sum of successors size.
516 E : if (!bb->successors().empty())
517 E : size += kMaxBranchSize;
518 E : }
519 :
520 E : return size;
521 E : }
522 :
523 : } // namespace
524 :
525 : bool InliningTransform::TransformBasicBlockSubGraph(
526 : const TransformPolicyInterface* policy,
527 : BlockGraph* block_graph,
528 : BasicBlockSubGraph* subgraph,
529 : ApplicationProfile* profile,
530 E : SubGraphProfile* subgraph_profile) {
531 E : DCHECK_NE(reinterpret_cast<TransformPolicyInterface*>(NULL), policy);
532 E : DCHECK_NE(reinterpret_cast<BlockGraph*>(NULL), block_graph);
533 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
534 E : DCHECK_NE(reinterpret_cast<ApplicationProfile*>(NULL), profile);
535 E : DCHECK_NE(reinterpret_cast<SubGraphProfile*>(NULL), subgraph_profile);
536 :
537 E : const BlockGraph::Block* caller = subgraph->original_block();
538 E : DCHECK_NE(reinterpret_cast<const BlockGraph::Block*>(NULL), caller);
539 :
540 : // Apply the decomposition policy to the caller.
541 E : if (!policy->BlockIsSafeToBasicBlockDecompose(caller))
542 E : return true;
543 :
544 : // The current block will be rebuilt and erased from the block graph. To avoid
545 : // dangling pointers, the block is removed from the decomposed cache.
546 E : subgraph_cache_.erase(caller->id());
547 :
548 : // Iterates through each basic block.
549 : BasicBlockSubGraph::BBCollection::iterator bb_iter =
550 E : subgraph->basic_blocks().begin();
551 E : for (; bb_iter != subgraph->basic_blocks().end(); ++bb_iter) {
552 E : BasicCodeBlock* bb = BasicCodeBlock::Cast(*bb_iter);
553 E : if (bb == NULL)
554 E : continue;
555 :
556 : // Iterates through each instruction.
557 E : BasicBlock::Instructions::iterator inst_iter = bb->instructions().begin();
558 E : while (inst_iter != bb->instructions().end()) {
559 E : const Instruction& instr = *inst_iter;
560 E : BasicBlock::Instructions::iterator call_iter = inst_iter;
561 E : ++inst_iter;
562 :
563 : // Match a direct call-site.
564 E : BlockGraph::Block* callee = NULL;
565 E : if (!MatchDirectCall(instr, &callee))
566 E : continue;
567 :
568 : // Avoid self recursion inlining.
569 : // Apply the decomposition policy to the callee.
570 : if (caller == callee ||
571 E : !policy->BlockIsSafeToBasicBlockDecompose(callee)) {
572 E : continue;
573 : }
574 :
575 E : if (MatchEmptyBody(callee)) {
576 : // Body is empty, remove call-site.
577 E : bb->instructions().erase(call_iter);
578 E : continue;
579 : }
580 :
581 E : if (MatchGetProgramCounter(callee)) {
582 : // TODO(etienneb): Implement Get Program Counter with a fixup.
583 i : continue;
584 : }
585 :
586 : // Keep only potential candidates.
587 E : if (callee->size() > kCodeSizeThreshold)
588 i : continue;
589 :
590 E : size_t subgraph_size = 0;
591 E : ScopedSubgraph callee_subgraph;
592 E : size_t return_constant = 0;
593 E : BasicCodeBlock* body = NULL;
594 E : BasicBlockReference target;
595 E : MatchKind match_kind = kInvalidMatch;
596 :
597 : // Look in the subgraph cache for an already decomposed subgraph size for
598 : // an optimized version of the callee block.
599 E : SubGraphCache::iterator look = subgraph_cache_.find(callee->id());
600 E : if (look != subgraph_cache_.end()) {
601 i : subgraph_size = look->second;
602 i : } else {
603 : // Decompose it. This cannot fail because
604 : // BlockIsSafeToBasicBlockDecompose is performed before.
605 E : CHECK(DecomposeCalleeBlock(callee, &callee_subgraph));
606 :
607 : // Heuristic to determine the callee size after inlining.
608 : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL),
609 E : callee_subgraph.get());
610 E : subgraph_size = EstimateSubgraphSize(callee_subgraph.get());
611 :
612 : // Cache the resulting size.
613 E : subgraph_cache_[callee->id()] = subgraph_size;
614 : }
615 :
616 : // Heuristic to determine whether to inline or not the callee subgraph.
617 E : bool candidate_for_inlining = false;
618 :
619 : // For a small callee, try to replace callee instructions in-place.
620 : // This kind of inlining is always a win.
621 E : size_t callsite_size = instr.size();
622 E : if (subgraph_size <= callsite_size + kColdCodeSizeThreshold)
623 E : candidate_for_inlining = true;
624 :
625 : // TODO(etienneb): Add more rules based on profile data.
626 :
627 E : if (!candidate_for_inlining)
628 E : continue;
629 :
630 : // If not already decomposed (cached), decompose it.
631 E : if (callee_subgraph.get() == NULL) {
632 i : CHECK(DecomposeCalleeBlock(callee, &callee_subgraph));
633 : }
634 :
635 : if (MatchTrivialBody(*callee_subgraph, &match_kind, &return_constant,
636 : &target, &body) &&
637 : InlineTrivialBody(match_kind, subgraph, return_constant, target, body,
638 E : call_iter, &bb->instructions())) {
639 : // Inlining successful, remove call-site.
640 E : bb->instructions().erase(call_iter);
641 E : } else {
642 : // Inlining was unsuccessful, avoid any further inlining of this block.
643 E : subgraph_cache_[callee->id()] = kHugeBlockSize;
644 : }
645 E : }
646 E : }
647 :
648 E : return true;
649 E : }
650 :
651 : } // namespace transforms
652 : } // namespace optimize
|