| blob | cf00b0dd2ce3f32cc22888801e2bbc40ee8a6da3 |
1 /* -*- mode: C; c-basic-offset: 3; -*- */
3 /*---------------------------------------------------------------*/
4 /*--- begin ir_opt.c ---*/
5 /*---------------------------------------------------------------*/
7 /*
8 This file is part of Valgrind, a dynamic binary instrumentation
9 framework.
11 Copyright (C) 2004-2017 OpenWorks LLP
12 info@open-works.net
14 This program is free software; you can redistribute it and/or
15 modify it under the terms of the GNU General Public License as
16 published by the Free Software Foundation; either version 2 of the
17 License, or (at your option) any later version.
19 This program is distributed in the hope that it will be useful, but
20 WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 General Public License for more details.
24 You should have received a copy of the GNU General Public License
25 along with this program; if not, write to the Free Software
26 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
27 02110-1301, USA.
29 The GNU General Public License is contained in the file COPYING.
31 Neither the names of the U.S. Department of Energy nor the
32 University of California nor the names of its contributors may be
33 used to endorse or promote products derived from this software
34 without prior written permission.
35 */
46 /* Set to 1 for lots of debugging output. */
47 #define DEBUG_IROPT 0
49 /* Set to 1 to gather some statistics. Currently only for sameIRExprs. */
50 #define STATS_IROPT 0
53 /* What iropt does, 29 Dec 04.
55 It takes an IRSB and produces a new one with the same meaning,
56 defined thus:
58 After execution of the new BB, all guest state and guest memory is
59 the same as after execution of the original. This is true
60 regardless of how the block was exited (at the end vs side exit).
62 In addition, parts of the guest state will be identical to that
63 created by execution of the original at the following observation
64 points:
66 * In a dirty helper call, any parts of the guest state that the
67 helper states that it reads or modifies will be up to date.
68 Also, guest memory will be up to date. Parts of the guest state
69 not marked as being read or modified by the helper cannot be
70 assumed to be up-to-date at the point where the helper is called.
72 * If iropt_register_updates == VexRegUpdSpAtMemAccess :
73 The guest state is only up to date only as explained above
74 (i.e. at SB exits and as specified by dirty helper call).
75 Also, the stack pointer register is up to date at memory
76 exception points (as this is needed for the stack extension
77 logic in m_signals.c).
79 * If iropt_register_updates == VexRegUpdUnwindregsAtMemAccess :
80 Immediately prior to any load or store, those parts of the guest
81 state marked as requiring precise exceptions will be up to date.
82 Also, guest memory will be up to date. Parts of the guest state
83 not marked as requiring precise exceptions cannot be assumed to
84 be up-to-date at the point of the load/store.
86 * If iropt_register_updates == VexRegUpdAllregsAtMemAccess:
87 Same as minimal, but all the guest state is up to date at memory
88 exception points.
90 * If iropt_register_updates == VexRegUpdAllregsAtEachInsn :
91 Guest state is up to date at each instruction.
93 The relative order of loads and stores (including loads/stores of
94 guest memory done by dirty helpers annotated as such) is not
95 changed. However, the relative order of loads with no intervening
96 stores/modifies may be changed.
98 Transformation order
99 ~~~~~~~~~~~~~~~~~~~~
101 There are three levels of optimisation, controlled by
102 vex_control.iropt_level. Define first:
104 "Cheap transformations" are the following sequence:
105 * Redundant-Get removal
106 * Redundant-Put removal
107 * Constant propagation/folding
108 * Dead code removal
109 * Specialisation of clean helper functions
110 * Dead code removal
112 "Expensive transformations" are the following sequence:
113 * CSE
114 * Folding of add/sub chains
115 * Redundant-GetI removal
116 * Redundant-PutI removal
117 * Dead code removal
119 Then the transformations are as follows, as defined by
120 vex_control.iropt_level:
122 Level 0:
123 * Flatten into atomic form.
125 Level 1: the following sequence:
126 * Flatten into atomic form.
127 * Cheap transformations.
129 Level 2: the following sequence
130 * Flatten into atomic form.
131 * Cheap transformations.
132 * If block contains any floating or vector types, CSE.
133 * If block contains GetI or PutI, Expensive transformations.
134 * Try unrolling loops. Three possible outcomes:
135 - No effect: do nothing more.
136 - Unrolled a loop, and block does not contain GetI or PutI:
137 Do: * CSE
138 * Dead code removal
139 - Unrolled a loop, and block contains GetI or PutI:
140 Do: * Expensive transformations
141 * Cheap transformations
142 */
144 /* Implementation notes, 29 Dec 04.
146 TODO (important): I think rPutI removal ignores precise exceptions
147 and is therefore in a sense, wrong. In the sense that PutIs are
148 assumed not to write parts of the guest state that we need to have
149 up-to-date at loads/stores. So far on x86 guest that has not
150 mattered since indeed only the x87 FP registers and tags are
151 accessed using GetI/PutI, and there is no need so far for them to
152 be up to date at mem exception points. The rPutI pass should be
153 fixed.
155 TODO: improve pessimistic handling of precise exceptions
156 in the tree builder.
158 TODO: check interaction of rGetI and dirty helpers.
160 F64i constants are treated differently from other constants.
161 They are not regarded as atoms, and instead lifted off and
162 bound to temps. This allows them to participate in CSE, which
163 is important for getting good performance for x86 guest code.
165 CSE up F64 literals (already doing F64is)
167 CSE: consider carefully the requirement for precise exns
168 prior to making CSE any more aggressive. */
171 /*---------------------------------------------------------------*/
172 /*--- Finite mappery, of a sort ---*/
173 /*---------------------------------------------------------------*/
175 /* General map from HWord-sized thing HWord-sized thing. Could be by
176 hashing, but it's not clear whether or not this would really be any
177 faster. */
179 typedef
184 Int size;
185 Int used;
186 }
187 HashHW;
190 {
198 }
201 /* Look up key in the map. */
204 {
205 Int i;
206 /* vex_printf("lookupHHW(%llx)\n", key ); */
212 }
213 }
215 }
218 /* Add key->val to the map. Replaces any existing binding for key. */
221 {
223 /* vex_printf("addToHHW(%llx, %llx)\n", key, val); */
225 /* Find and replace existing binding, if any. */
230 }
231 }
233 /* Ensure a space is available. */
235 /* Copy into arrays twice the size. */
244 j++;
245 }
251 }
253 /* Finally, add it. */
259 }
262 /*---------------------------------------------------------------*/
263 /*--- Flattening out a BB into atomic SSA form ---*/
264 /*---------------------------------------------------------------*/
266 /* Non-critical helper, heuristic for reducing the number of tmp-tmp
267 copies made by flattening. If in doubt return False. */
270 {
279 }
281 /* Flatten out 'ex' so it is atomic, returning a new expression with
282 the same value, after having appended extra IRTemp assignments to
283 the end of 'bb'. */
286 {
287 Int i;
290 IRTemp t1;
318 }
329 }
362 newargs)));
374 /* Lift F64i constants out onto temps so they can be CSEd
375 later. */
382 /* Leave all other constants alone. */
384 }
394 }
395 }
398 /* Append a completely flattened form of 'st' to the end of 'bb'. */
401 {
402 Int i;
412 /* optimisation to reduce the amount of heap wasted
413 by the flattener */
416 /* general case, always correct */
419 }
430 /* optimisation, to reduce the number of tmp-tmp
431 copies generated */
434 /* general case, always correct */
437 }
487 }
493 }
517 }
518 }
522 {
523 Int i;
534 }
537 /*---------------------------------------------------------------*/
538 /*--- In-place removal of redundant GETs ---*/
539 /*---------------------------------------------------------------*/
541 /* Scan forwards, building up an environment binding (min offset, max
542 offset) pairs to values, which will either be temps or constants.
544 On seeing 't = Get(minoff,maxoff)', look up (minoff,maxoff) in the
545 env and if it matches, replace the Get with the stored value. If
546 there is no match, add a (minoff,maxoff) :-> t binding.
548 On seeing 'Put (minoff,maxoff) = t or c', first remove in the env
549 any binding which fully or partially overlaps with (minoff,maxoff).
550 Then add a new (minoff,maxoff) :-> t or c binding. */
552 /* Extract the min/max offsets from a guest state array descriptor. */
554 inline
557 {
563 }
565 /* Create keys, of the form ((minoffset << 16) | maxoffset). */
568 {
569 /* offset should fit in 16 bits. */
575 }
578 {
584 }
586 /* Supposing h has keys of the form generated by mk_key_GetPut and
587 mk_key_GetIPutI, invalidate any key which overlaps (k_lo
588 .. k_hi).
589 */
591 {
592 Int j;
595 /* invalidate any env entries which in any way overlap (k_lo
596 .. k_hi) */
597 /* vex_printf("invalidate %d .. %d\n", k_lo, k_hi ); */
607 else
608 /* overlap; invalidate */
610 }
611 }
615 {
619 HWord val;
627 /* Deal with Gets */
630 /* st is 't = Get(...)'. Look up in the environment and see
631 if the Get can be replaced. */
636 /* found it */
637 /* Note, we could do better here. If the types are
638 different we don't do the substitution, since doing so
639 could lead to invalidly-typed IR. An improvement would
640 be to stick in a reinterpret-style cast, although that
641 would make maintaining flatness more difficult. */
649 }
653 /* Not found, but at least we know that t and the Get(...)
654 are now associated. So add a binding to reflect that
655 fact. */
658 }
659 }
661 /* Deal with Puts: invalidate any env entries overlapped by this
662 Put */
671 }
676 }
677 else
679 /* Deal with dirty helpers which write or modify guest state.
680 Invalidate the entire env. We could do a lot better
681 here. */
688 }
690 /* dump the entire env (not clever, but correct ...) */
694 }
695 }
697 /* add this one to the env, if appropriate */
701 }
705 }
708 /*---------------------------------------------------------------*/
709 /*--- In-place removal of redundant PUTs ---*/
710 /*---------------------------------------------------------------*/
712 /* Find any Get uses in st and invalidate any partially or fully
713 overlapping ranges listed in env. Due to the flattening phase, the
714 only stmt kind we expect to find a Get on is IRStmt_WrTmp. */
720 VexRegisterUpdates pxControl
721 )
722 {
723 Int j;
725 Bool isGet;
731 /* This is the only interesting case. Deal with Gets in the RHS
732 expression. */
750 }
756 }
759 /* Be very conservative for dirty helper calls; dump the entire
760 environment. The helper might read guest state, in which
761 case it needs to be flushed first. Also, the helper might
762 access guest memory, in which case all parts of the guest
763 state requiring precise exceptions needs to be flushed. The
764 crude solution is just to flush everything; we could easily
765 enough do a lot better if needed. */
766 /* Probably also overly-conservative, but also dump everything
767 if we hit a memory bus event (fence, lock, unlock). Ditto
768 AbiHints, CASs, LLs and SCs. */
772 /* fall through */
781 /* all other cases are boring. */
794 }
802 }
825 }
828 /* This statement accesses memory. So we might need to dump all parts
829 of the environment corresponding to guest state that may not
830 be reordered with respect to memory references. That means
831 at least the stack pointer. */
834 /* Precise exceptions required at mem access.
835 Flush all guest state. */
840 /* We need to dump the stack pointer
841 (needed for stack extension in m_signals.c).
842 preciseMemExnsFn will use vex_control.iropt_register_updates
843 to verify only the sp is to be checked. */
844 /* fallthrough */
849 /* Just flush the minimal amount required, as computed by
850 preciseMemExnsFn. */
855 }
858 // VexRegUpdAllregsAtEachInsn cannot happen here.
859 // fall through
863 }
866 }
869 /* Scan backwards, building up a set of (min offset, max
870 offset) pairs, indicating those parts of the guest state
871 for which the next event is a write.
873 On seeing a conditional exit, empty the set.
875 On seeing 'Put (minoff,maxoff) = t or c', if (minoff,maxoff) is
876 completely within the set, remove the Put. Otherwise, add
877 (minoff,maxoff) to the set.
879 On seeing 'Get (minoff,maxoff)', remove any part of the set
880 overlapping (minoff,maxoff). The same has to happen for any events
881 which implicitly read parts of the guest state: dirty helper calls
882 and loads/stores.
883 */
888 VexRegisterUpdates pxControl
889 )
890 {
892 Bool isPut;
900 /* Initialise the running env with the fact that the final exit
901 writes the IP (or, whatever it claims to write. We don't
902 care.) */
906 /* And now scan backwards through the statements. */
913 /* Deal with conditional exits. */
915 //Bool re_add;
916 /* Need to throw out from the env, any part of it which
917 doesn't overlap with the guest state written by this exit.
918 Since the exit only writes one section, it's simplest to
919 do this: (1) check whether env contains a write that
920 completely overlaps the write done by this exit; (2) empty
921 out env; and (3) if (1) was true, add the write done by
922 this exit.
924 To make (1) a bit simpler, merely search for a write that
925 exactly matches the one done by this exit. That's safe
926 because it will fail as often or more often than a full
927 overlap check, and failure to find an overlapping write in
928 env is the safe case (we just nuke env if that
929 happens). */
930 //vassert(isIRAtom(st->Ist.Exit.guard));
931 /* (1) */
932 //key = mk_key_GetPut(st->Ist.Exit.offsIP,
933 // typeOfIRConst(st->Ist.Exit.dst));
934 //re_add = lookupHHW(env, NULL, key);
935 /* (2) */
938 /* (3) */
939 //if (0 && re_add)
940 // addToHHW(env, (HWord)key, 0);
942 }
944 /* Deal with Puts */
960 }
962 /* See if any single entry in env overlaps this Put. This is
963 simplistic in that the transformation is valid if, say, two
964 or more entries in the env overlap this Put, but the use of
965 lookupHHW will only find a single entry which exactly
966 overlaps this Put. This is suboptimal but safe. */
968 /* This Put is redundant because a later one will overwrite
969 it. So NULL (nop) it out. */
973 }
976 /* We can't demonstrate that this Put is redundant, so add it
977 to the running collection. */
979 }
981 }
983 /* Deal with Gets. These remove bits of the environment since
984 appearance of a Get means that the next event for that slice
985 of the guest state is no longer a write, but a read. Also
986 deals with implicit reads of guest state needed to maintain
987 precise exceptions. */
989 }
990 }
993 /*---------------------------------------------------------------*/
994 /*--- Constant propagation and folding ---*/
995 /*---------------------------------------------------------------*/
997 #if STATS_IROPT
998 /* How often sameIRExprs was invoked */
1000 /* How often sameIRExprs recursed through IRTemp assignments */
1002 /* How often sameIRExprs found identical IRExprs */
1004 /* How often recursing through assignments to IRTemps helped
1005 establishing equality. */
1007 /* Whether or not recursing through an IRTemp assignment helped
1008 establishing IRExpr equality for a given sameIRExprs invocation. */
1010 /* Whether or not a given sameIRExprs invocation recursed through an
1011 IRTemp assignment */
1013 /* Maximum number of nodes ever visited when comparing two IRExprs. */
1017 /* Count the number of nodes visited for a given sameIRExprs invocation. */
1020 /* Do not visit more than NODE_LIMIT nodes when comparing two IRExprs.
1021 This is to guard against performance degradation by visiting large
1022 trees without success. */
1023 #define NODE_LIMIT 30
1026 /* The env in this section is a map from IRTemp to IRExpr*,
1027 that is, an array indexed by IRTemp. */
1029 /* Do both expressions compute the same value? The answer is generally
1030 conservative, i.e. it will report that the expressions do not compute
1031 the same value when in fact they do. The reason is that we do not
1032 keep track of changes in the guest state and memory. Thusly, two
1033 Get's, GetI's or Load's, even when accessing the same location, will be
1034 assumed to compute different values. After all the accesses may happen
1035 at different times and the guest state / memory can have changed in
1036 the meantime.
1038 XXX IMPORTANT XXX the two expressions must have the same IR type.
1039 DO NOT CALL HERE WITH DIFFERENTLY-TYPED EXPRESSIONS. */
1041 /* JRS 20-Mar-2012: split sameIRExprs_aux into a fast inlineable
1042 wrapper that deals with the common tags-don't-match case, and a
1043 slower out of line general case. Saves a few insns. */
1048 inline
1050 {
1053 }
1057 {
1067 #if STATS_IROPT
1070 #endif
1072 }
1078 /* Guest state / memory could have changed in the meantime. */
1104 }
1106 }
1115 }
1126 /* Not very likely to be "same". */
1128 }
1131 }
1133 inline
1135 {
1136 Bool same;
1141 #if STATS_IROPT
1154 }
1157 /* Debugging-only hack (not used in production runs): make a guess
1158 whether sameIRExprs might assert due to the two args being of
1159 different types. If in doubt return False. Is only used when
1160 --vex-iropt-level > 0, that is, vex_control.iropt_verbosity > 0.
1161 Bad because it duplicates functionality from typeOfIRExpr. See
1162 comment on the single use point below for rationale. */
1163 static
1165 {
1169 /* The only interesting case */
1173 }
1176 }
1178 }
1181 /* Is this literally IRExpr_Const(IRConst_U32(0)) ? */
1183 {
1187 }
1189 /* Is this literally IRExpr_Const(IRConst_U64(0)) ?
1190 Currently unused; commented out to avoid compiler warning */
1191 #if 0
1193 {
1197 }
1198 #endif
1200 /* Is this literally IRExpr_Const(IRConst_V128(0)) ? */
1202 {
1206 }
1208 /* Is this literally IRExpr_Const(IRConst_V128(1...1)) ? */
1210 {
1214 }
1216 /* Is this literally IRExpr_Const(IRConst_V256(0)) ? */
1218 {
1222 }
1224 /* Is this an integer constant with value 0 ? */
1226 {
1236 }
1237 }
1239 /* Is this an integer constant with value 1---1b ? */
1241 {
1251 }
1252 }
1255 {
1259 }
1261 /* Make a zero which has the same type as the result of the given
1262 primop. */
1264 {
1279 }
1280 }
1282 /* Make a value containing all 1-bits, which has the same type as the
1283 result of the given primop. */
1285 {
1306 }
1307 }
1309 /* Helpers for folding Clz32/64. */
1311 {
1312 UInt i;
1316 }
1318 /*NOTREACHED*/
1320 }
1323 {
1324 UInt i;
1328 }
1330 /*NOTREACHED*/
1332 }
1334 /* V64 holds 8 summary-constant bits in V128/V256 style. Convert to
1335 the corresponding real constant. */
1336 //XXX re-check this before use
1337 //static ULong de_summarise_V64 ( UChar v64 )
1338 //{
1339 // ULong r = 0;
1340 // if (v64 & (1<<0)) r |= 0x00000000000000FFULL;
1341 // if (v64 & (1<<1)) r |= 0x000000000000FF00ULL;
1342 // if (v64 & (1<<2)) r |= 0x0000000000FF0000ULL;
1343 // if (v64 & (1<<3)) r |= 0x00000000FF000000ULL;
1344 // if (v64 & (1<<4)) r |= 0x000000FF00000000ULL;
1345 // if (v64 & (1<<5)) r |= 0x0000FF0000000000ULL;
1346 // if (v64 & (1<<6)) r |= 0x00FF000000000000ULL;
1347 // if (v64 & (1<<7)) r |= 0xFF00000000000000ULL;
1348 // return r;
1349 //}
1351 /* Helper for arbitrary expression pattern matching in flat IR. If
1352 'e' is a reference to a tmp, look it up in env -- repeatedly, if
1353 necessary -- until it resolves to a non-tmp. Note that this can
1354 return NULL if it can't resolve 'e' to a new expression, which will
1355 be the case if 'e' is instead defined by an IRStmt (IRDirty or
1356 LLSC). */
1358 {
1359 /* Why is this loop guaranteed to terminate? Because all tmps must
1360 have definitions before use, hence a tmp cannot be bound
1361 (directly or indirectly) to itself. */
1366 }
1368 }
1370 /* Similar to |chase|, but follows at most one level of tmp reference. */
1372 {
1375 else
1377 }
1380 {
1381 Int shift;
1386 /* UNARY ops */
1389 /* cases where the arg is a const */
1434 }
1441 }
1460 }
1480 )));
1485 )));
1519 }
1525 }
1531 }
1537 }
1540 0xFFFFFFFFULL
1549 }
1556 }
1563 }
1570 }
1576 )));
1582 )));
1587 )));
1594 else
1597 }
1602 else
1605 }
1613 }
1621 }
1628 }
1634 }
1636 /* For these vector ones, can't fold all cases, but at least
1637 do the most obvious one. Could do better here using
1638 summarise/desummarise of vector constants, but too
1639 difficult to verify; hence just handle the zero cases. */
1646 }
1648 }
1655 }
1657 }
1664 }
1666 }
1673 }
1675 }
1677 /* Even stupider (although still correct ..) */
1685 }
1687 }
1690 /* Could do better here -- only need to look at the bottom 64 bits
1691 of the argument, really. */
1697 }
1699 }
1707 /* other cases (identities, etc) */
1710 // PopCount64( And64( Add64(x,-1), Not64(x) ) ) ==> CtzNat64(x)
1711 // bindings:
1712 // a1:And64( a11:Add64(a111:x,a112:-1), a12:Not64(a121:x) )
1718 // a1 is established
1724 // a11 is established
1730 // a12 is established
1736 // a111 and a121 need to be the same temp.
1739 // Finally, a112 must be a 64-bit version of -1.
1742 // Match established. Transform.
1745 nomatch:
1747 }
1756 /* BINARY ops */
1759 /* cases where both args are consts */
1762 /* -- Or -- */
1789 /* -- Xor -- */
1816 /* -- And -- */
1843 /* -- Add -- */
1860 /* -- Sub -- */
1877 /* -- Max32U -- */
1884 }
1886 /* -- Mul -- */
1899 /* very paranoid */
1910 }
1912 /* -- Shl -- */
1930 /* -- Sar -- */
1932 /* paranoid ... */
1940 }
1942 }
1944 /* paranoid ... */
1952 }
1954 }
1956 /* -- Shr -- */
1958 /* paranoid ... */
1966 }
1968 }
1970 /* paranoid ... */
1978 }
1980 }
1982 /* -- CmpEQ -- */
1994 /* -- CmpNE -- */
2017 /* -- CmpLEU -- */
2029 /* -- CmpLES -- */
2041 /* -- CmpLTS -- */
2053 /* -- CmpLTU -- */
2065 /* -- CmpORD -- */
2067 /* very paranoid */
2075 }
2078 }
2081 }
2083 /* -- nHLto2n -- */
2089 ));
2092 /* We can't fold this, because there is no way to
2093 express he result in IR, but at least pretend to
2094 handle it, so as to stop getting blasted with
2095 no-rule-for-this-primop messages. */
2097 /* For this vector one, can't fold all cases, but at
2098 least do the most obvious one. Could do better here
2099 using summarise/desummarise of vector constants, but
2100 too difficult to verify; hence just handle the zero
2101 cases. */
2109 }
2111 }
2112 /* Same reasoning for the 256-bit version. */
2120 }
2122 }
2124 /* -- V128 stuff -- */
2126 /* This turns up a lot in Memcheck instrumentation of
2127 Icc generated code. I don't know why. */
2134 }
2136 }
2140 }
2144 /* other cases (identities, etc) */
2151 /* Shl32/Shl64/Shr64/Sar64(x,0) ==> x */
2155 }
2156 /* Shl32/Shl64/Shr64(0,x) ==> 0 */
2160 }
2165 /* Shr32/Sar32(x,0) ==> x */
2169 }
2177 /* Or8/Or16/Or32/Or64/Max32U(x,0) ==> x */
2181 }
2182 /* Or8/Or16/Or32/Or64/Max32U(0,x) ==> x */
2186 }
2187 /* Or8/Or16/Or32/Or64/Max32U(x,1---1b) ==> 1---1b */
2188 /* Or8/Or16/Or32/Or64/Max32U(1---1b,x) ==> 1---1b */
2192 }
2193 /* Or8/Or16/Or32/Or64/Max32U(t,t) ==> t, for some IRTemp t */
2197 }
2201 /* Add8(t,t) ==> t << 1.
2202 Memcheck doesn't understand that
2203 x+x produces a defined least significant bit, and it seems
2204 simplest just to get rid of the problem by rewriting it
2205 out, since the opportunity to do so exists. */
2210 }
2213 /* NB no Add16(t,t) case yet as no known test case exists */
2217 /* Add32/Add64(x,0) ==> x */
2221 }
2222 /* Add32/Add64(0,x) ==> x */
2226 }
2227 /* Add32/Add64(t,t) ==> t << 1. Same rationale as for Add8. */
2233 }
2238 /* Sub32/Sub64(x,0) ==> x */
2242 }
2243 /* Sub32/Sub64(t,t) ==> 0, for some IRTemp t */
2247 }
2250 /* Sub8x16(x,0) ==> x */
2254 }
2261 /* And8/And16/And32/And64(x,1---1b) ==> x */
2265 }
2266 /* And8/And16/And32/And64(1---1b,x) ==> x */
2270 }
2271 /* And8/And16/And32/And64(x,0) ==> 0 */
2275 }
2276 /* And8/And16/And32/And64(0,x) ==> 0 */
2280 }
2281 /* And8/And16/And32/And64(t,t) ==> t, for some IRTemp t */
2285 }
2290 /* And8/And16/AndV128/AndV256(t,t)
2291 ==> t, for some IRTemp t */
2295 }
2296 /* Deal with either arg zero. Could handle other And
2297 cases here too. */
2308 }
2309 /* AndV128(t,1...1) ==> t. The amd64 front end generates these
2310 for *CMP{P,S}{S,D} etc. */
2315 }
2316 }
2321 /* V128/V256(t,t) ==> t, for some IRTemp t */
2325 }
2326 /* OrV128(t,0) ==> t */
2331 }
2335 }
2336 }
2337 /* OrV256(t,0) ==> t */
2342 }
2343 //Disabled because there's no known test case right now.
2344 //if (isZeroV256(e->Iex.Binop.arg1)) {
2345 // e2 = e->Iex.Binop.arg2;
2346 // break;
2347 //}
2348 }
2357 /* Xor8/16/32/64/V128(t,t) ==> 0, for some IRTemp t */
2361 }
2362 /* XorV128(t,0) ==> t */
2367 }
2368 //Disabled because there's no known test case right now.
2369 //if (isZeroV128(e->Iex.Binop.arg1)) {
2370 // e2 = e->Iex.Binop.arg2;
2371 // break;
2372 //}
2374 /* Xor8/16/32/64(0,t) ==> t */
2378 }
2379 /* Xor8/16/32/64(t,0) ==> t */
2383 }
2384 }
2388 /* CmpNE32(t,t) ==> 0, for some IRTemp t */
2392 }
2393 /* CmpNE32(1Uto32(b), 0) ==> b */
2400 }
2401 }
2413 }
2418 }
2419 }
2423 /* ITE */
2424 /* is the discriminant is a constant? */
2426 /* assured us by the IR type rules */
2430 }
2431 else
2432 /* are the arms identical? (pretty weedy test) */
2436 }
2440 /* not considered */
2442 }
2444 /* Show cases where we've found but not folded 'op(t,t)'. Be
2445 careful not to call sameIRExprs with values of different types,
2446 though, else it will assert (and so it should!). We can't
2447 conveniently call typeOfIRExpr on the two args without a whole
2448 bunch of extra plumbing to pass in a type env, so just use a
2449 hacky test to check the arguments are not anything that might
2450 sameIRExprs to assert. This is only OK because this kludge is
2451 only used for debug printing, not for "real" operation. For
2452 "real" operation (ie, all other calls to sameIRExprs), it is
2453 essential that the to args have the same type.
2455 The "right" solution is to plumb the containing block's
2456 IRTypeEnv through to here and use typeOfIRExpr to be sure. But
2457 that's a bunch of extra parameter passing which will just slow
2458 down the normal case, for no purpose. */
2468 }
2470 /* Show the overall results of folding. */
2475 }
2479 unhandled:
2480 # if 0
2484 # else
2489 }
2491 # endif
2492 }
2495 /* Apply the subst to a simple 1-level expression -- guaranteed to be
2496 1-level due to previous flattening pass. */
2499 {
2509 }
2510 /* not bound in env */
2523 );
2537 );
2538 }
2550 );
2551 }
2560 );
2567 );
2575 );
2578 Int i;
2583 }
2587 args2
2588 );
2589 }
2599 );
2605 }
2606 }
2609 /* Apply the subst to stmt, then fold the result as much as possible.
2610 Much simplified due to stmt being previously flattened. As a
2611 result of this, the stmt may wind up being turned into a no-op.
2612 */
2614 {
2615 # if 0
2619 # endif
2629 );
2635 );
2647 }
2650 /* This is the one place where an expr (st->Ist.WrTmp.data) is
2651 allowed to be more than just a constant or a tmp. */
2655 );
2664 );
2675 /* The condition on this store has folded down to a constant. */
2682 }
2683 }
2685 }
2688 /* This is complicated. If the guard folds down to 'false',
2689 we can replace it with an assignment 'dst := alt', but if
2690 the guard folds down to 'true', we can't conveniently
2691 replace it with an unconditional load, because doing so
2692 requires generating a new temporary, and that is not easy
2693 to do at this point. */
2702 /* The condition on this load has folded down to a constant. */
2705 /* The load is not going to happen -- instead 'alt' is
2706 assigned to 'dst'. */
2710 /* The load is always going to happen. We want to
2711 convert to an unconditional load and assign to 'dst'
2712 (IRStmt_WrTmp). Problem is we need an extra temp to
2713 hold the loaded value, but none is available.
2714 Instead, reconstitute the conditional load (with
2715 folded args, of course) and let the caller of this
2716 routine deal with the problem. */
2717 }
2718 }
2720 }
2739 );
2741 }
2753 : NULL
2754 );
2757 Int i;
2766 }
2774 }
2775 }
2777 }
2795 /* Interesting. The condition on this exit has folded down to
2796 a constant. */
2799 /* exit is never going to happen, so dump the statement. */
2803 /* Hmmm. The exit has become unconditional. Leave it
2804 as it is for now, since we'd have to truncate the BB
2805 at this point, which is tricky. Such truncation is
2806 done later by the dead-code elimination pass. */
2807 /* fall out into the reconstruct-the-exit code. */
2809 /* really a misuse of vex_control.iropt_verbosity */
2811 }
2812 }
2815 }
2820 }
2821 }
2825 {
2826 Int i;
2831 /* Keep track of IRStmt_LoadGs that we need to revisit after
2832 processing all the other statements. */
2840 /* Set up the env with which travels forward. This holds a
2841 substitution, mapping IRTemps to IRExprs. The environment
2842 is to be applied as we move along. Keys are IRTemps.
2843 Values are IRExpr*s.
2844 */
2848 /* For each original SSA-form stmt ... */
2851 /* First apply the substitution to the current stmt. This
2852 propagates in any constants and tmp-tmp assignments
2853 accumulated prior to this point. As part of the subst_Stmt
2854 call, also then fold any constant expressions resulting. */
2858 /* perhaps st2 is already a no-op? */
2863 /* Deal with some post-folding special cases. */
2866 /* If the statement has been folded into a no-op, forget
2867 it. */
2871 /* If the statement assigns to an IRTemp add it to the
2872 running environment. This is for the benefit of copy
2873 propagation and to allow sameIRExpr look through
2874 IRTemps. */
2879 /* 't1 = t2' -- don't add to BB; will be optimized out */
2883 /* 't = const' && 'const != F64i' -- don't add to BB
2884 Note, we choose not to propagate const when const is an
2885 F64i, so that F64i literals can be CSE'd later. This
2886 helps x86 floating point code generation. */
2890 }
2891 /* else add it to the output, as normal */
2893 }
2899 /* The guard has folded to a constant, and that
2900 constant must be 1:I1, since subst_and_fold_Stmt
2901 folds out the case 0:I1 by itself. */
2904 /* Add a NoOp here as a placeholder, and make a note of
2905 where it is in the output block. Afterwards we'll
2906 come back here and transform the NoOp and the LoadG
2907 into a load-convert pair. The fixups[] entry
2908 refers to the inserted NoOp, and we expect to find
2909 the relevant LoadG immediately after it. */
2914 }
2915 }
2916 /* And always add the LoadG to the output, regardless. */
2918 }
2922 }
2924 /* Not interesting, copy st2 into the output block. */
2926 }
2928 # if STATS_IROPT
2932 # endif
2938 /* Process any leftover unconditional LoadGs that we noticed
2939 in the main pass. */
2943 /* Carefully verify that the LoadG has the expected form. */
2953 /* Figure out the load and result types, and the implied
2954 conversion operation. */
2967 }
2968 /* Replace the placeholder NoOp by the required unconditional
2969 load. */
2974 /* Replace the LoadG by a conversion from the loaded value's
2975 type to the required result type. */
2981 }
2984 }
2987 /*---------------------------------------------------------------*/
2988 /*--- Dead code (t = E) removal ---*/
2989 /*---------------------------------------------------------------*/
2991 /* As a side effect, also removes all code following an unconditional
2992 side exit. */
2994 /* The type of the HashHW map is: a map from IRTemp to nothing
2995 -- really just operating a set or IRTemps.
2996 */
2998 inline
3000 {
3002 }
3005 {
3006 Int i;
3051 }
3052 }
3055 {
3056 Int i;
3084 }
3091 }
3116 }
3129 }
3130 }
3133 /* Is this literally IRExpr_Const(IRConst_U1(False)) ? */
3135 {
3139 }
3141 /* Is this literally IRExpr_Const(IRConst_U1(True)) ? */
3143 {
3147 }
3150 /* Note, this destructively modifies the given IRSB. */
3152 /* Scan backwards through statements, carrying a set of IRTemps which
3153 are known to be used after the current point. On encountering 't =
3154 E', delete the binding if it is not used. Otherwise, add any temp
3155 uses to the set and keep on moving backwards.
3157 As an enhancement, the first (backwards) pass searches for IR exits
3158 with always-taken conditions and notes the location of the earliest
3159 one in the block. If any such are found, a second pass copies the
3160 exit destination and jump kind to the bb-end. Then, the exit and
3161 all statements following it are turned into no-ops.
3162 */
3165 {
3174 /* start off by recording IRTemp uses in the next field. */
3177 /* First pass */
3179 /* Work backwards through the stmts */
3185 /* take note of any unconditional exits */
3191 /* it's an IRTemp which never got used. Delete it. */
3196 }
3198 }
3199 else
3203 /* This is a dirty helper which will never get called.
3204 Delete it. */
3206 }
3208 /* Note any IRTemp uses made by the current statement. */
3210 }
3211 }
3213 /* Optional second pass: if any unconditional exits were found,
3214 delete them and all following statements. */
3218 i_unconditional_exit);
3221 bb->next
3223 bb->jumpkind
3225 bb->offsIP
3229 }
3230 }
3233 /*---------------------------------------------------------------*/
3234 /*--- Specialisation of helper function calls, in ---*/
3235 /*--- collaboration with the front end ---*/
3236 /*---------------------------------------------------------------*/
3238 static
3242 )
3243 {
3244 Int i;
3260 /* the front end can't think of a suitable replacement */
3263 /* We got something better. Install it in the bb. */
3274 }
3275 }
3280 }
3283 /*---------------------------------------------------------------*/
3284 /*--- Determination of guest state aliasing relationships ---*/
3285 /*---------------------------------------------------------------*/
3287 /* These are helper functions for CSE and GetI/PutI transformations.
3289 Determine, to the extent possible, the relationship between two
3290 guest state accesses. The possible outcomes are:
3292 * Exact alias. These two accesses denote precisely the same
3293 piece of the guest state.
3295 * Definitely no alias. These two accesses are guaranteed not to
3296 overlap any part of the guest state.
3298 * Unknown -- if neither of the above can be established.
3300 If in doubt, return Unknown. */
3302 typedef
3304 GSAliasing;
3307 /* Produces the alias relation between an indexed guest
3308 state access and a non-indexed access. */
3310 static
3313 {
3323 /* Could probably do better here if required. For the moment
3324 however just claim not to know anything more. */
3326 }
3329 /* Produces the alias relation between two indexed guest state
3330 accesses. */
3332 static
3336 )
3337 {
3339 Int iters;
3341 /* First try hard to show they don't alias. */
3347 /* So the two arrays at least partially overlap. To get any
3348 further we'll have to be sure that the descriptors are
3349 identical. */
3353 /* The descriptors are identical. Now the only difference can be
3354 in the index expressions. If they cannot be shown to be
3355 identical, we have to say we don't know what the aliasing
3356 relation will be. Now, since the IR is flattened, the index
3357 expressions should be atoms -- either consts or tmps. So that
3358 makes the comparison simple. */
3364 /* Ok, the index expressions are identical. So now the only way
3365 they can be different is in the bias. Normalise this
3366 paranoidly, to reliably establish equality/non-equality. */
3368 /* So now we know that the GetI and PutI index the same array
3369 with the same base. Are the offsets the same, modulo the
3370 array size? Do this paranoidly. */
3378 iters++;
3381 }
3388 /* Finally, biasP and biasG are normalised into the range
3389 0 .. descrP/G->nElems - 1. And so we can establish
3390 equality/non-equality. */
3393 }
3396 /*---------------------------------------------------------------*/
3397 /*--- Common Subexpression Elimination ---*/
3398 /*---------------------------------------------------------------*/
3400 /* Expensive in time and space. */
3402 /* Uses two environments:
3403 a IRTemp -> IRTemp mapping
3404 a mapping from AvailExpr* to IRTemp
3405 */
3407 typedef
3411 }
3412 TmpOrConst;
3415 {
3425 }
3426 }
3429 {
3434 /* Names should be the same too, but we don't bother to
3435 check. */
3436 }
3438 }
3440 /* Convert an atomic IRExpr* to a TmpOrConst. */
3442 {
3453 /* Getting here is a serious error. It means that the
3454 presented arg isn't an IR atom, as it should be. */
3456 }
3457 }
3459 /* Convert a TmpOrConst to an atomic IRExpr*. */
3461 {
3466 }
3467 }
3469 /* Convert a NULL terminated IRExpr* vector to an array of
3470 TmpOrConsts, and a length. */
3474 {
3476 /* We have to make two passes, one to count, one to copy. */
3478 ;
3481 /* and now copy .. */
3486 }
3487 }
3489 typedef
3492 CCall, Load
3495 /* unop(tmp) */
3497 IROp op;
3498 IRTemp arg;
3500 /* binop(tmp,tmp) */
3502 IROp op;
3503 IRTemp arg1;
3504 IRTemp arg2;
3506 /* binop(tmp,const) */
3508 IROp op;
3509 IRTemp arg1;
3510 IRConst con2;
3512 /* binop(const,tmp) */
3514 IROp op;
3515 IRConst con1;
3516 IRTemp arg2;
3518 /* F64i-style const */
3520 ULong f64i;
3522 /* ITE(tmp,tmp,tmp) */
3524 IRTemp co;
3525 IRTemp e1;
3526 IRTemp e0;
3528 /* ITE(tmp,tmp,const) */
3530 IRTemp co;
3531 IRTemp e1;
3532 IRConst con0;
3534 /* ITE(tmp,const,tmp) */
3536 IRTemp co;
3537 IRConst con1;
3538 IRTemp e0;
3540 /* ITE(tmp,const,const) */
3542 IRTemp co;
3543 IRConst con1;
3544 IRConst con0;
3546 /* GetI(descr,tmp,bias)*/
3549 IRTemp ix;
3550 Int bias;
3552 /* Clean helper call */
3556 Int nArgs;
3557 IRType retty;
3559 /* Load(end,ty,addr) */
3561 IREndness end;
3562 IRType ty;
3563 TmpOrConst addr;
3566 }
3567 AvailExpr;
3570 {
3626 }
3627 }
3628 }
3631 }
3637 }
3640 }
3641 }
3644 {
3703 }
3706 vec);
3707 }
3713 }
3714 }
3716 inline
3718 {
3719 HWord res;
3720 /* env :: IRTemp -> IRTemp */
3723 else
3725 }
3727 inline
3730 {
3731 /* env :: IRTemp -> IRTemp */
3734 }
3735 }
3738 {
3739 /* env :: IRTemp -> IRTemp */
3779 }
3781 }
3787 }
3788 }
3791 {
3802 }
3814 }
3822 }
3831 }
3840 }
3853 }
3861 }
3870 }
3878 }
3879 }
3880 }
3891 }
3897 /* Ok to share only the cee, since it is immutable. */
3900 /* irExprVec_to_TmpOrConsts will assert if the args are
3901 neither tmps nor constants, but that's ok .. that's all they
3902 should be. */
3906 );
3910 /* If the caller of do_cse_BB has requested that loads also
3911 be CSEd, convert them into AvailExprs. If not, we'll just
3912 return NULL here, and the load never becomes considered
3913 "available", which effectively disables CSEing of them, as
3914 desired. */
3922 }
3927 }
3930 }
3933 /* The BB is modified in-place. Returns True if any changes were
3934 made. The caller can choose whether or not loads should be CSEd.
3935 In the normal course of things we don't do that, since CSEing loads
3936 is something of a dodgy proposition if the guest program is doing
3937 some screwy stuff to do with races and spinloops. */
3940 {
3946 Bool invalidate;
3956 /* Iterate forwards over the stmts.
3957 On seeing "t = E", where E is one of the AvailExpr forms:
3958 let E' = apply tenv substitution to E
3959 search aenv for E'
3960 if a mapping E' -> q is found,
3961 replace this stmt by "t = q"
3962 and add binding t -> q to tenv
3963 else
3964 add binding E' -> t to aenv
3965 replace this stmt by "t = E'"
3967 Other statements are only interesting to the extent that they
3968 might invalidate some of the expressions in aenv. So there is
3969 an invalidate-bindings check for each statement seen.
3970 */
3974 /* ------ BEGIN invalidate aenv bindings ------ */
3975 /* This is critical: remove from aenv any E' -> .. bindings
3976 which might be invalidated by this statement. The only
3977 vulnerable kind of bindings are the GetI and Load kinds.
3978 Dirty call - dump (paranoia level -> 2)
3979 Store - dump (ditto)
3980 Put, PutI - dump unless no-overlap is proven (.. -> 1)
3981 Uses getAliasingRelation_IC and getAliasingRelation_II
3982 to do the no-overlap assessments needed for Put/PutI.
3983 */
3996 }
4011 /* Loads can be invalidated by anything that could
4012 possibly touch memory. But in that case we
4013 should have |paranoia| == 2 and we won't get
4014 here. So there's nothing to do; we don't have to
4015 invalidate the load. */
4016 }
4017 else
4026 }
4027 else
4036 puti->bias
4039 }
4040 else
4042 }
4047 }
4051 /* ------ ENV invalidate aenv bindings ------ */
4053 /* ignore not-interestings */
4059 /* ignore if not of AvailExpr form */
4063 /* vex_printf("considering: " ); ppIRStmt(st); vex_printf("\n"); */
4065 /* apply tenv */
4068 /* search aenv for eprime, unfortunately the hard way */
4074 /* A binding E' -> q was found. Replace stmt by "t = q" and
4075 note the t->q binding in tenv. */
4076 /* (this is the core of the CSE action) */
4082 /* No binding was found, so instead we add E' -> t to our
4083 collection of available expressions, replace this stmt
4084 with "t = E'", and move on. */
4087 }
4088 }
4090 /*
4091 ppIRSB(bb);
4092 sanityCheckIRSB(bb, Ity_I32);
4093 vex_printf("\n\n");
4094 */
4096 }
4099 /*---------------------------------------------------------------*/
4100 /*--- Add32/Sub32 chain collapsing ---*/
4101 /*---------------------------------------------------------------*/
4103 /* ----- Helper functions for Add32/Sub32 chain collapsing ----- */
4105 /* Is this expression "Add32(tmp,const)" or "Sub32(tmp,const)" ? If
4106 yes, set *tmp and *i32 appropriately. *i32 is set as if the
4107 root node is Add32, not Sub32. */
4110 {
4124 }
4127 /* Figure out if tmp can be expressed as tmp2 +32 const, for some
4128 other tmp2. Scan backwards from the specified start point -- an
4129 optimisation. */
4132 IRTemp tmp,
4134 {
4136 IRTemp vv;
4140 /* the (var, con) pair contain the current 'representation' for
4141 'tmp'. We start with 'tmp + 0'. */
4145 /* Scan backwards to see if tmp can be replaced by some other tmp
4146 +/- a constant. */
4158 }
4160 /* no earlier binding for var .. ill-formed IR */
4163 /* so, did we find anything interesting? */
4170 }
4173 /* ------- Main function for Add32/Sub32 chain collapsing ------ */
4176 {
4186 /* Try to collapse 't1 = Add32/Sub32(t2, con)'. */
4191 /* So e1 is of the form Add32(var,con) or Sub32(var,-con).
4192 Find out if var can be expressed as var2 + con2. */
4198 }
4210 );
4214 }
4215 }
4218 }
4220 /* Try to collapse 't1 = GetI[t2, con]'. */
4231 }
4238 con2));
4242 }
4244 }
4246 /* Perhaps st is PutI[t, con] ? */
4256 }
4261 con2,
4266 }
4268 }
4271 }
4274 /*---------------------------------------------------------------*/
4275 /*--- PutI/GetI transformations ---*/
4276 /*---------------------------------------------------------------*/
4278 /* Given the parts (descr, tmp, bias) for a GetI, scan backwards from
4279 the given starting point to find, if any, a PutI which writes
4280 exactly the same piece of guest state, and so return the expression
4281 that the PutI writes. This is the core of PutI-GetI forwarding. */
4283 static
4286 {
4287 Int j;
4289 GSAliasing relation;
4297 }
4299 /* Scan backwards in bb from startHere to find a suitable PutI
4300 binding for (descrG, ixG, biasG), if any. */
4308 /* Non-indexed Put. This can't give a binding, but we do
4309 need to check it doesn't invalidate the search by
4310 overlapping any part of the indexed guest state. */
4312 relation
4319 /* we're OK; keep going */
4322 /* relation == UnknownAlias || relation == ExactAlias */
4323 /* If this assertion fails, we've found a Put which writes
4324 an area of guest state which is read by a GetI. Which
4325 is unlikely (although not per se wrong). */
4327 /* This Put potentially writes guest state that the GetI
4328 reads; we must fail. */
4330 }
4331 }
4340 puti->bias
4341 );
4344 /* This PutI definitely doesn't overlap. Ignore it and
4345 keep going. */
4347 }
4350 /* We don't know if this PutI writes to the same guest
4351 state that the GetI, or not. So we have to give up. */
4353 }
4355 /* Otherwise, we've found what we're looking for. */
4362 /* Be conservative. If the dirty call has any guest effects at
4363 all, give up. We could do better -- only give up if there
4364 are any guest writes/modifies. */
4367 }
4371 /* No valid replacement was found. */
4373 }
4377 /* Assuming pi is a PutI stmt, is s2 identical to it (in the sense
4378 that it writes exactly the same piece of guest state) ? Safe
4379 answer: False. */
4382 {
4394 )
4395 == ExactAlias
4396 );
4397 }
4400 /* Assuming pi is a PutI stmt, is s2 a Get/GetI/Put/PutI which might
4401 overlap it? Safe answer: True. Note, we could do a lot better
4402 than this if needed. */
4404 static
4407 )
4408 {
4409 GSAliasing relation;
4425 /* just be paranoid ... these should be rare. */
4429 /* This is unbelievably lame, but it's probably not
4430 significant from a performance point of view. Really, a
4431 CAS is a load-store op, so it should be safe to say False.
4432 However .. */
4436 /* If the dirty call has any guest effects at all, give up.
4437 Probably could do better. */
4444 relation
4449 );
4457 relation
4461 );
4463 }
4467 relation
4473 );
4475 }
4477 relation
4482 );
4484 }
4495 }
4497 have_relation:
4500 else
4502 }
4506 /* ---------- PutI/GetI transformations main functions --------- */
4508 /* Remove redundant GetIs, to the extent that they can be detected.
4509 bb is modified in-place. */
4511 static
4513 {
4514 Int i;
4531 /* Make sure we're doing a type-safe transformation! */
4539 }
4541 }
4542 }
4543 }
4545 }
4548 /* Remove redundant PutIs, to the extent which they can be detected.
4549 bb is modified in-place. */
4551 static
4553 {
4564 /* Ok, search forwards from here to see if we can find another
4565 PutI which makes this one redundant, and dodging various
4566 hazards. Search forwards:
4567 * If conditional exit, give up (because anything after that
4568 does not postdominate this put).
4569 * If a Get which might overlap, give up (because this PutI
4570 not necessarily dead).
4571 * If a Put which is identical, stop with success.
4572 * If a Put which might overlap, but is not identical, give up.
4573 * If a dirty helper call which might write guest state, give up.
4574 * If a Put which definitely doesn't overlap, or any other
4575 kind of stmt, continue.
4576 */
4583 /* success! */
4586 }
4588 /* give up */
4591 /* give up; could do better here */
4594 /* give up */
4596 }
4603 }
4605 }
4607 }
4608 }
4611 /*---------------------------------------------------------------*/
4612 /*--- Loop unrolling ---*/
4613 /*---------------------------------------------------------------*/
4615 /* Adjust all tmp values (names) in e by delta. e is destructively
4616 modified. */
4619 {
4620 Int i;
4664 }
4665 }
4667 /* Adjust all tmp values (names) in st by delta. st is destructively
4668 modified. */
4671 {
4672 Int i;
4707 }
4715 }
4741 }
4750 }
4751 }
4754 /* If possible, return a loop-unrolled version of bb0. The original
4755 is changed. If not possible, return NULL. */
4757 /* The two schemas considered are:
4759 X: BODY; goto X
4761 which unrolls to (eg) X: BODY;BODY; goto X
4763 and
4765 X: BODY; if (c) goto X; goto Y
4766 which trivially transforms to
4767 X: BODY; if (!c) goto Y; goto X;
4768 so it falls in the scope of the first case.
4770 X and Y must be literal (guest) addresses.
4771 */
4774 {
4780 n_stmts++;
4781 }
4788 }
4794 }
4801 }
4807 }
4811 {
4813 Bool xxx_known;
4819 Int unroll_factor;
4824 /* First off, figure out if we can unroll this loop. Do this
4825 without modifying bb0. */
4833 /* Extract the next-guest address. If it isn't a literal, we
4834 have to give up. */
4840 /* The BB ends in a jump to a literal location. */
4845 }
4850 /* Now we know the BB ends to a jump to a literal location. If
4851 it's a jump to itself (viz, idiom #1), move directly to the
4852 unrolling stage, first cloning the bb so the original isn't
4853 modified. */
4862 }
4864 /* Search for the second idiomatic form:
4865 X: BODY; if (c) goto X; goto Y
4866 We know Y, but need to establish that the last stmt
4867 is 'if (c) goto X'.
4868 */
4890 /* If this assertion fails, we have some kind of type error. */
4894 /* We didn't find either idiom. Give up. */
4897 /* Ok, we found idiom #2. Copy the BB, switch around the xxx and
4898 yyy values (which makes it look like idiom #1), and go into
4899 unrolling proper. This means finding (again) the last stmt, in
4900 the copied BB. */
4913 /* The next bunch of assertions should be true since we already
4914 found and checked the last stmt in the original bb. */
4930 /* switch the xxx and yyy fields around */
4937 }
4939 /* negate the test condition */
4943 /* --- The unroller proper. Both idioms are by now --- */
4944 /* --- now converted to idiom 1. --- */
4946 do_unroll:
4962 /* deltaIRStmt destructively modifies the stmt, but
4963 that's OK since bb2 is a complete fresh copy of bb1. */
4966 }
4967 }
4973 }
4975 /* Flattening; sigh. The unroller succeeds in breaking flatness
4976 by negating the test condition. This should be fixed properly.
4977 For the moment use this shotgun approach. */
4979 }
4982 /*---------------------------------------------------------------*/
4983 /*--- The tree builder ---*/
4984 /*---------------------------------------------------------------*/
4986 /* This isn't part of IR optimisation. Really it's a pass done prior
4987 to instruction selection, which improves the code that the
4988 instruction selector can produce. */
4990 /* --- The 'tmp' environment is the central data structure here --- */
4992 /* The number of outstanding bindings we're prepared to track.
4993 The number of times the env becomes full and we have to dump
4994 the oldest binding (hence reducing code quality) falls very
4995 rapidly as the env size increases. 8 gives reasonable performance
4996 under most circumstances. */
4997 #define A_NENV 10
4999 /* An interval. Used to record the bytes in the guest state accessed
5000 by a Put[I] statement or by (one or more) Get[I] expression(s). In
5001 case of several Get[I] expressions, the lower/upper bounds are recorded.
5002 This is conservative but cheap.
5003 E.g. a Put of 8 bytes at address 100 would be recorded as [100,107].
5004 E.g. an expression that reads 8 bytes at offset 100 and 4 bytes at
5005 offset 200 would be recorded as [100,203] */
5006 typedef
5008 Bool present;
5009 Int low;
5010 Int high;
5011 }
5012 Interval;
5016 {
5019 }
5023 {
5033 }
5034 }
5037 /* bindee == NULL === slot is not in use
5038 bindee != NULL === slot is in use
5039 */
5040 typedef
5042 IRTemp binder;
5044 Bool doesLoad;
5045 /* Record the bytes of the guest state BINDEE reads from. */
5046 Interval getInterval;
5047 }
5048 ATmpInfo;
5052 {
5053 Int i;
5058 else
5061 }
5062 }
5064 /* --- Tree-traversal fns --- */
5066 /* Traverse an expr, and detect if any part of it reads memory or does
5067 a Get. Be careful ... this really controls how much the
5068 tree-builder can reorder the code, so getting it right is critical.
5069 */
5071 {
5072 Int i;
5110 }
5119 }
5126 }
5127 }
5130 /* Add a binding to the front of the env and slide all the rest
5131 backwards. It should be the case that the last slot is free. */
5133 {
5134 Int i;
5144 }
5146 /* Given uses :: array of UShort, indexed by IRTemp
5147 Add the use-occurrences of temps in this expression
5148 to the env.
5149 */
5151 {
5152 Int i;
5208 }
5209 }
5212 /* Given uses :: array of UShort, indexed by IRTemp
5213 Add the use-occurrences of temps in this statement
5214 to the env.
5215 */
5217 {
5218 Int i;
5246 }
5253 }
5278 }
5290 }
5291 }
5293 /* Look up a binding for tmp in the env. If found, return the bound
5294 expression, and set the env's binding to NULL so it is marked as
5295 used. If not found, return NULL. */
5298 {
5299 Int i;
5305 }
5306 }
5308 }
5310 /* Traverse e, looking for temps. For each observed temp, see if env
5311 contains a binding for the temp, and if so return the bound value.
5312 The env has the property that any binding it holds is
5313 'single-shot', so once a binding is used, it is marked as no longer
5314 available, by setting its .bindee field to NULL. */
5318 }
5321 }
5324 {
5327 /* Or32( CmpwNEZ32(x), CmpwNEZ32(y) ) --> CmpwNEZ32( Or32( x, y ) ) */
5335 /* Since X has type Ity_I1 we can simplify:
5336 CmpNE32(1Uto32(X),0)) ==> X */
5343 }
5344 /* no reduction rule applies */
5346 }
5349 {
5352 /* CmpwNEZ64( CmpwNEZ64 ( x ) ) --> CmpwNEZ64 ( x ) */
5355 /* CmpwNEZ64( Or64 ( CmpwNEZ64(x), y ) ) --> CmpwNEZ64( Or64( x, y ) ) */
5359 Iop_CmpwNEZ64,
5363 /* CmpwNEZ64( Or64 ( x, CmpwNEZ64(y) ) ) --> CmpwNEZ64( Or64( x, y ) ) */
5367 Iop_CmpwNEZ64,
5373 /* CmpNEZ64( Left64(x) ) --> CmpNEZ64(x) */
5376 /* CmpNEZ64( 1Uto64(X) ) --> X */
5381 /* CmpwNEZ32( CmpwNEZ32 ( x ) ) --> CmpwNEZ32 ( x ) */
5386 /* CmpNEZ32( Left32(x) ) --> CmpNEZ32(x) */
5389 /* CmpNEZ32( 1Uto32(X) ) --> X */
5392 /* CmpNEZ32( 64to32( CmpwNEZ64(X) ) ) --> CmpNEZ64(X) */
5397 /* CmpNEZ8( 1Uto8(X) ) --> X */
5402 /* Left32( Left32(x) ) --> Left32(x) */
5407 /* Left64( Left64(x) ) --> Left64(x) */
5412 /* ZeroHI64ofV128( ZeroHI64ofV128(x) ) --> ZeroHI64ofV128(x) */
5417 /* 32to1( 1Uto32 ( x ) ) --> x */
5420 /* 32to1( CmpwNEZ32 ( x )) --> CmpNEZ32(x) */
5425 /* 64to1( 1Uto64 ( x ) ) --> x */
5428 /* 64to1( CmpwNEZ64 ( x )) --> CmpNEZ64(x) */
5433 /* 64to32( 32Uto64 ( x )) --> x */
5436 /* 64to32( 8Uto64 ( x )) --> 8Uto32(x) */
5442 /* 32Uto64( 8Uto32( x )) --> 8Uto64(x) */
5445 /* 32Uto64( 16Uto32( x )) --> 16Uto64(x) */
5448 /* 32Uto64(64to32( Shr64( 32Uto64(64to32(x)), sh ))
5449 --> Shr64( 32Uto64(64to32(x)), sh )) */
5454 Iop_64to32)) {
5456 }
5457 /* 32Uto64(64to32( Shl64( 32Uto64(64to32(x)), sh ))
5458 --> 32Uto64(64to32( Shl64( x, sh )) */
5463 Iop_64to32)) {
5464 return
5466 Iop_32Uto64,
5468 Iop_64to32,
5470 Iop_Shl64,
5473 )));
5474 }
5478 /* 1Sto32( CmpNEZ8( 32to8( 1Uto32( CmpNEZ32( x ))))) -> CmpwNEZ32(x) */
5483 Iop_CmpNEZ32)) {
5487 }
5492 }
5493 /* no reduction rule applies */
5495 }
5498 {
5501 Int i;
5512 args2
5513 );
5522 );
5530 );
5537 );
5543 );
5548 );
5554 );
5560 );
5567 }
5568 }
5570 /* Same deal as atbSubst_Expr, except for stmts. */
5573 {
5574 Int i;
5585 );
5591 );
5598 }
5605 }
5610 );
5615 );
5630 );
5648 );
5657 );
5669 }
5674 }
5675 }
5677 inline
5679 {
5681 }
5683 inline
5687 VexRegisterUpdates pxControl,
5689 )
5690 {
5691 Int i;
5692 Interval interval;
5694 /* Passing the guest state pointer opens the door to modifying the
5695 guest state under the covers. It's not allowed, but let's be
5696 extra conservative and assume the worst. */
5700 /* Assume all guest state is written. */
5705 }
5706 }
5708 /* Check the side effects on the guest state */
5722 pxControl)) {
5724 }
5727 }
5728 }
5731 }
5733 /* Return an interval if st modifies the guest state. Via
5734 requiresPreciseMemExns return whether or not that modification
5735 requires precise exceptions. */
5739 VexRegisterUpdates pxControl,
5741 )
5742 {
5743 Interval interval;
5750 *requiresPreciseMemExns
5756 }
5763 /* We quietly assume here that all segments are contiguous and there
5764 are no holes. This is to avoid a loop. The assumption is conservative
5765 in the sense that we might report that precise memory exceptions are
5766 needed when in fact they are not. */
5767 *requiresPreciseMemExns
5769 pxControl);
5774 }
5779 requiresPreciseMemExns);
5787 }
5788 }
5793 VexRegisterUpdates pxControl
5794 )
5795 {
5798 Interval putInterval;
5809 /* Phase 1. Scan forwards in bb, counting use occurrences of each
5810 temp. Also count occurrences in the bb->next field. Take the
5811 opportunity to also find the maximum guest address in the block,
5812 since that will be needed later for deciding when we can safely
5813 elide event checks. */
5830 }
5833 }
5835 }
5838 # if 0
5844 }
5845 # endif
5847 /* Phase 2. Scan forwards in bb. For each statement in turn:
5849 If the env is full, emit the end element. This guarantees
5850 there is at least one free slot in the following.
5852 On seeing 't = E', occ(t)==1,
5853 let E'=env(E)
5854 delete this stmt
5855 add t -> E' to the front of the env
5856 Examine E' and set the hints for E' appropriately
5857 (doesLoad? doesGet?)
5859 On seeing any other stmt,
5860 let stmt' = env(stmt)
5861 remove from env any 't=E' binds invalidated by stmt
5862 emit the invalidated stmts
5863 emit stmt'
5864 compact any holes in env
5865 by sliding entries towards the front
5867 Finally, apply env to bb->next.
5868 */
5873 }
5875 /* The stmts in bb are being reordered, and we are guaranteed to
5876 end up with no more than the number we started with. Use i to
5877 be the cursor of the current stmt examined and j <= i to be that
5878 for the current stmt being written.
5879 */
5887 /* Ensure there's at least one space in the env, by emitting
5888 the oldest binding if necessary. */
5892 j++;
5895 }
5897 /* Consider current stmt. */
5901 /* optional extra: dump dead bindings as we find them.
5902 Removes the need for a prior dead-code removal pass. */
5906 }
5909 /* ok, we have 't = E', occ(t)==1. Do the abovementioned
5910 actions. */
5915 /* don't advance j, as we are deleting this stmt and instead
5916 holding it temporarily in the env. */
5918 }
5920 /* we get here for any other kind of statement. */
5921 /* 'use up' any bindings required by the current statement. */
5924 /* Now, before this stmt, dump any bindings in env that it
5925 invalidates. These need to be dumped in the order in which
5926 they originally entered env -- that means from oldest to
5927 youngest. */
5929 /* putInterval/stmtStores characterise what the stmt under
5930 consideration does, or might do (sidely safe @ True). */
5932 Bool putRequiresPreciseMemExns;
5935 &putRequiresPreciseMemExns
5936 );
5938 /* be True if this stmt writes memory or might do (==> we don't
5939 want to reorder other loads or stores relative to it). Also,
5940 both LL and SC fall under this classification, since we
5941 really ought to be conservative and not reorder any other
5942 memory transactions relative to them. */
5943 stmtStores
5953 /* Compare the actions of this stmt with the actions of
5954 binding 'k', to see if they invalidate the binding. */
5955 invalidateMe
5957 /* a store invalidates loaded data */
5959 /* a put invalidates get'd data, if they overlap */
5962 /* a put invalidates loaded data. That means, in essense, that
5963 a load expression cannot be substituted into a statement
5964 that follows the put. But there is nothing wrong doing so
5965 except when the put statement requries precise exceptions.
5966 Think of a load that is moved past a put where the put
5967 updates the IP in the guest state. If the load generates
5968 a segfault, the wrong address (line number) would be
5969 reported. */
5971 putRequiresPreciseMemExns)
5972 /* probably overly conservative: a memory bus event
5973 invalidates absolutely everything, so that all
5974 computation prior to it is forced to complete before
5975 proceeding with the event (fence,lock,unlock). */
5977 /* also be (probably overly) paranoid re AbiHints */
5979 );
5982 j++;
5985 }
5986 }
5988 /* Slide in-use entries in env up to the front */
5993 m++;
5994 }
5995 }
5998 }
6000 /* finally, emit the substituted statement */
6002 /* vex_printf("**2 "); ppIRStmt(bb->stmts[j]); vex_printf("\n"); */
6003 j++;
6008 /* Finally ... substitute the ->next field as much as possible, and
6009 dump any left-over bindings. Hmm. Perhaps there should be no
6010 left over bindings? Or any left-over bindings are
6011 by definition dead? */
6016 }
6019 /*---------------------------------------------------------------*/
6020 /*--- MSVC specific transformation hacks ---*/
6021 /*---------------------------------------------------------------*/
6023 /* The purpose of all this is to find MSVC's idiom for non-constant
6024 bitfield assignment, "a ^ ((a ^ b) & c)", and transform it into
6025 gcc's idiom "(a & ~c) | (b & c)". Motivation is that Memcheck has
6026 generates a lot of false positives from the MSVC version because it
6027 doesn't understand that XORing an undefined bit with itself gives a
6028 defined result.
6030 This isn't a problem for the simple case "x ^ x", because iropt
6031 folds it to a constant zero before Memcheck ever sees it. But in
6032 this case we have an intervening "& c" which defeats the simple
6033 case. So we have to carefully inspect all expressions rooted at an
6034 XOR to see if any of them match "a ^ ((a ^ b) & c)", or any of the
6035 7 other variants resulting from swapping the order of arguments to
6036 the three binary operations. If we get a match, we then replace
6037 the tree with "(a & ~c) | (b & c)", and Memcheck is happy.
6039 The key difficulty is to spot the two uses of "a". To normalise
6040 the IR to maximise the chances of success, we first do a CSE pass,
6041 with CSEing of loads enabled, since the two "a" expressions may be
6042 loads, which need to be commoned up. Then we do a constant folding
6043 pass, so as to remove any tmp-to-tmp assignment chains that would
6044 make matching the original expression more difficult.
6045 */
6048 /* Helper function for debug printing */
6051 {
6055 }
6065 }
6072 }
6088 }
6089 }
6091 /* Spot a ^ ((a ^ b) & c) for a,b and c tmp-or-const (atoms)
6092 or any of the other 7 variants generated by switching the order
6093 of arguments to the outer ^, the inner ^ and the &.
6094 */
6099 {
6100 # define ISBIN(_e,_op) ((_e) && (_e)->tag == Iex_Binop \
6101 && (_e)->Iex.Binop.op == (_op))
6102 # define ISATOM(_e) isIRAtom(_e)
6103 # define STEP(_e) chase1(env, (_e))
6104 # define LL(_e) ((_e)->Iex.Binop.arg1)
6105 # define RR(_e) ((_e)->Iex.Binop.arg2)
6109 /* This is common to all 8 cases */
6112 /* -----and------ */
6113 /* --xor--- */
6114 /* find variant 1: a1 ^ ((a2 ^ b) & c) */
6115 /* find variant 2: a1 ^ ((b ^ a2) & c) */
6132 }
6138 }
6140 v34:
6141 /* -----and------ */
6142 /* --xor--- */
6143 /* find variant 3: ((a2 ^ b) & c) ^ a1 */
6144 /* find variant 4: ((b ^ a2) & c) ^ a1 */
6161 }
6167 }
6169 v56:
6170 /* -----and------ */
6171 /* --xor--- */
6172 /* find variant 5: a1 ^ (c & (a2 ^ b)) */
6173 /* find variant 6: a1 ^ (c & (b ^ a2)) */
6191 }
6198 }
6200 v78:
6201 /* -----and------ */
6202 /* --xor--- */
6203 /* find variant 7: (c & (a2 ^ b)) ^ a1 */
6204 /* find variant 8: (c & (b ^ a2)) ^ a1 */
6221 }
6227 }
6229 fail:
6232 # undef ISBIN
6233 # undef ISATOM
6234 # undef STEP
6235 # undef LL
6236 # undef RR
6237 }
6239 /* If |e| is of the form a ^ ((a ^ b) & c) (or any of the 7 other
6240 variants thereof generated by switching arguments around), return
6241 the IRExpr* for (a & ~c) | (b & c). Else return NULL. */
6243 {
6270 }
6282 /* It's vitally important that the returned aa, bb and cc are
6283 atoms -- either constants or tmps. If it's anything else
6284 (eg, a GET) then incorporating them in a tree at this point
6285 in the SB may erroneously pull them forwards (eg of a PUT
6286 that originally was after the GET) and so transform the IR
6287 wrongly. spotBitfieldAssignment should guarantee only to
6288 give us atoms, but we check here anyway. */
6293 opOR,
6296 );
6297 }
6299 }
6302 /* SB is modified in-place. Visit all the IRExprs and, for those
6303 which are allowed to be non-atomic, perform the XOR transform if
6304 possible. This makes |sb| be non-flat, but that's ok, the caller
6305 can re-flatten it. Returns True iff any changes were made. */
6307 {
6308 Int i;
6311 /* Make the tmp->expr environment, so we can use it for
6312 chasing expressions. */
6325 }
6343 }
6345 /* This is the one place where an expr (st->Ist.WrTmp.data) is
6346 allowed to be more than just a constant or a tmp. */
6347 IRExpr* mb_new_data
6350 //ppIRSB(sb);
6352 //ppIRSB(sb);
6354 }
6356 }
6367 }
6374 }
6383 }
6393 }
6399 }
6400 }
6402 }
6413 }
6414 }
6418 }
6422 {
6423 // Normalise as much as we can. This is the one-and-only place
6424 // where we call do_cse_BB with allowLoadsToBeCSEd set to True.
6427 // CSEing might have created dead code. Remove it.
6430 }
6432 // Visit all atoms, do the transformation proper. bb is modified
6433 // in-place.
6437 // The transformation generates non-flat expressions, so we now
6438 // need to re-flatten the block.
6440 }
6443 }
6446 /*---------------------------------------------------------------*/
6447 /*--- iropt main ---*/
6448 /*---------------------------------------------------------------*/
6453 /* Do a simple cleanup pass on bb. This is: redundant Get removal,
6454 redundant Put removal, constant propagation, dead code removal,
6455 clean helper specialisation, and dead code removal (again).
6456 */
6459 static
6464 VexRegisterUpdates pxControl
6465 )
6466 {
6471 }
6475 }
6479 }
6485 }
6491 }
6498 }
6501 }
6504 /* Do some more expensive transformations on bb, which are aimed at
6505 optimising as much as possible in the presence of GetI and PutI. */
6507 static
6509 {
6515 }
6518 }
6521 /* Scan a flattened BB to look for signs that more expensive
6522 optimisations might be useful:
6523 - find out if there are any GetIs and PutIs
6524 - find out if there are any floating or vector-typed temporaries
6525 */
6530 {
6565 }
6580 }
6587 }
6608 }
6620 bad:
6623 }
6624 }
6625 }
6628 /* ---------------- The main iropt entry point. ---------------- */
6630 /* exported from this file */
6631 /* Rules of the game:
6633 - IRExpr/IRStmt trees should be treated as immutable, as they
6634 may get shared. So never change a field of such a tree node;
6635 instead construct and return a new one if needed.
6636 */
6643 VexRegisterUpdates pxControl,
6644 Addr guest_addr,
6645 VexArch guest_arch
6646 )
6647 {
6654 n_total++;
6656 /* First flatten the block out, since all other
6657 phases assume flat code. */
6664 }
6666 /* If at level 0, stop now. */
6669 /* Now do a preliminary cleanup pass, and figure out if we also
6670 need to do 'expensive' optimisations. Expensive optimisations
6671 are deemed necessary if the block contains any GetIs or PutIs.
6672 If needed, do expensive transformations and then another cheap
6673 cleanup pass. */
6678 /* Translating Thumb2 code produces a lot of chaff. We have to
6679 work extra hard to get rid of it. */
6684 }
6687 }
6691 /* Peer at what we have, to decide how much more effort to throw
6692 at it. */
6696 /* If any evidence of FP or Vector activity, CSE, as that
6697 tends to mop up all manner of lardy code to do with
6698 rounding modes. Don't bother if hasGetIorPutI since that
6699 case leads into the expensive transformations, which do
6700 CSE anyway. */
6703 }
6706 Bool cses;
6707 n_expensive++;
6713 /* Potentially common up GetIs */
6718 }
6720 ///////////////////////////////////////////////////////////
6721 // BEGIN MSVC optimised code transformation hacks
6724 // END MSVC optimised code transformation hacks
6725 ///////////////////////////////////////////////////////////
6727 /* Now have a go at unrolling simple (single-BB) loops. If
6728 successful, clean up the results as much as possible. */
6739 /* at least do CSE and dead code removal */
6742 }
6744 }
6746 }
6749 }
6752 /*---------------------------------------------------------------*/
6753 /*--- end ir_opt.c ---*/
6754 /*---------------------------------------------------------------*/