Lines Matching refs:we
22 explains how we could combine equal functions correctly, keeping module valid.
31 cover only common cases, and thus avoid cases when after minor code changes we
39 code fundamentals. In this article we suppose reader is familiar with
77 again and again, and yet you don't understand why we implemented it that way.
98 Do we need to merge functions? Obvious thing is: yes that's a quite possible
99 case, since usually we *do* have duplicates. And it would be good to get rid of
100 them. But how to detect such a duplicates? The idea is next: we split functions
101 onto small bricks (parts), then we compare "bricks" amount, and if it equal,
106 (let's assume we have only one address space), one function stores 64-bit
108 mentioned above, and if functions are identical, except the parameter type (we
109 could consider it as a part of function type), then we can treat ``uint64_t``
120 Let's briefly consider possible options about how and what we have to implement
129 As the second step, we should merge equal functions. So it should be a "merger"
133 Having such a routines in our hands, we can process whole module, and merge all
136 In this case, we have to compare every function with every another function. As
137 reader could notice, this way seems to be quite expensive. Of course we could
141 Can we reach another level? Could we introduce logarithmical search, or random
148 means, that every function part must be taken into account. That means we have
155 We could introduce total ordering among the functions set, once we had it we
173 *random-access* approach we could use the same comparison algorithm. During
174 comparison we exit once we find the difference, but here we might have to scan
176 "total-ordering", we will track every numbers and flags, but instead of
177 comparison, we should get numbers sequence and then create the hash number. So,
191 implemented “<” operator among the functions set (below we explain how it works
196 case we remove them from ``FnTree``, and mark them as to be rescanned, namely
220 Let's recall our task: for every function *F* from module *M*, we have to find
238 Of course it means, that we have to maintain
251 Below, we will use the next operations:
262 reader to keep this file open nearby, so we could use it as a reference for
265 Now we're ready to proceed to the next chapter and see how it works.
269 At first, let's define how exactly we compare complex objects.
275 #. For two trees *T1* and *T2* we perform *depth-first-traversal* and have
313 bodies, if we see the usage of *LHS*'s *i*-th argument in *LHS*'s body, then,
314 we want to see usage of *RHS*'s *i*-th argument at the same place in *RHS*'s
315 body, otherwise functions are different. On this stage we grant the preference
316 to those we met later in function body (value we met first would be *less*).
327 So, using this walk we get BBs from *left* and *right* in the same order, and
331 We also associate BBs with each other, like we did it with function formal
342 2. If left and right types are equal, return 0. Otherwise we need to give
378 way. If we get -1 or 1 on some stage, return it. Otherwise return 0.
380 8. Steps 1-6 describe all the possible cases, if we passed steps 1-6 and didn't
388 This method gives us an answer on a very curious quesion: whether we could treat
392 Consider situation when we're looking at the same place in left function "*FL*"
406 What we expect from equal functions? At the same place, in functions "*FL*" and
407 "*FR*" we expect to see *equal* values, or values *defined* at the same place
425 and we also declare that *pf0* < *pf1*, and thus *pg0* < *pf1*.
431 opcode "*instr1*" from *g*; here we have equal types and opcodes, but "*pf1* is
437 What we assiciate in cmpValues?
441 * BasicBlock instances. In basic-block enumeration loop we associate *i*-th
445 * Instruction operands. Note, we can meet *Value* here we have never seen
450 * If right constant could be losslessly bit-casted to the left one, then we
456 But, in general, we need to implement antisymmetric relation. As it was
457 mentioned above, to understand what is *less*, we can use order in which we
462 Every time we run top-level compare method, we initialize two identical maps
470 To add value *V* we need to perform the next procedure:
477 Then we can check whether left and right values met at the same time with simple
482 Of course, we can combine insertion and comparison:
493 1. we have to start from the bad news. Consider function self and
509 we can't convert to less-equal-greater comparison. It is a seldom case, 4-5
510 functions of 10000 (checked on test-suite), and, we hope, reader would
513 2. If left/right *Value* is a constant, we have to compare them. Return 0 if it
520 find out whether values met at the same time, and thus are *associated*. Or we
521 need to put the rule: when we treat *L* < *R*. Now it is easy: just return
533 Now when *cmpValues* returns 0, we can proceed comparison procedure. Otherwise,
534 if we get (-1 or 1), we need to pass this result to the top level, and finish
544 2. If types are different, we still can check whether constants could be
565 * if both of them are pointers, good for us, we can proceed to step 3.
568 * otherwise we have no methods to prove bitcastability, and thus return
587 Mathematically it is equal to the next case: we encode left constant and right
634 So, if we get constant offset for both left and right *GEPs*, then compare it as
656 some significant attributes. For example we have to compare alignment for
662 for nodes comparison in a binary tree. So we can organize functions set into
680 1. Most wished case: when we can use alias and both of *F* and *G* are weak. We
683 source code). Well, this is a case when we can just replace *G* with *F*
684 everywhere, we use ``replaceAllUsesWith`` operation here (*RAUW*).
701 ok: we can use alias to *F* instead of *G* or change call instructions itself.
705 First consider the case when we have global aliases of one function name to
707 function. Though if we keep *F* alive and without major changes we can leave it
716 steps procedure instead. First of all, we must take into account, all functions
717 from whom *F* is called would be changed: since we change the call argument
718 (from *F* to *H*). If so we must to review these caller functions again after
723 V)`` we go through the all values that use value *V* (or *F* in our context).
724 If value is instruction, we go to function that holds this instruction and
725 mark it as to-be-analyzed-again (put to ``Deferred`` set), we also remove
728 2.2. Now we can do the replacement: call ``F->replaceAllUsesWith(H)``.
732 was used, we use *H* and it is alias to *F*, and everywhere *G* was used we
742 user is call instruction and *G* is used as what to be called), we replace it
748 We call ``writeThunkOrAlias(Function *F, Function *G)``. Here we try to replace
756 Otherwise we write thunk: some wrapper that has *G's* interface and calls *F*,
763 “Aliases act as *second name* for the aliasee value”. So we just want to create
786 In general it does the same as usual when we want to replace callee, except the
799 first chapter we have described how it works all-together. Author hopes, reader