• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2017-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license.
3  */
4 
5 package kotlinx.atomicfu.transformer
6 
7 import org.objectweb.asm.Opcodes.*
8 import org.objectweb.asm.Type
9 import org.objectweb.asm.tree.*
10 import kotlin.math.abs
11 
12 class FlowAnalyzer(
13     private val start: AbstractInsnNode?
14 ) {
15     private var cur: AbstractInsnNode? = null
16 
17     // the depth at which our atomic variable lies now (zero == top of stack),
18     // this ref at one slot below it (and we can choose to merge them!)
19     private var depth = 0
20 
abortnull21     private fun abort(msg: String): Nothing = abort(msg, cur)
22     private fun unsupported(): Nothing = abort("Unsupported operation on atomic variable")
23     private fun unrecognized(i: AbstractInsnNode): Nothing = abort("Unrecognized operation ${i.toText()}")
24 
25     private fun push(n: Int, forward: Boolean) {
26         if (!forward && abs(depth) < n) unsupported()
27         depth += n
28     }
29 
popnull30     private fun pop(n: Int, forward: Boolean) {
31         if (forward && depth < n) unsupported()
32         depth -= n
33     }
34 
35     // with stack top containing transformed variables analyses the following sequential data flow until consumed with:
36     //   * "astore" -- result is VarInsnNode
37     //   * "invokevirtual" on it -- result is MethodInsnNode
38     // All other outcomes produce transformation error
executenull39     fun execute(): AbstractInsnNode {
40         var i = start
41         while (i != null) {
42             cur = i
43             executeOne(i)?.let { return it }
44             i = i.next
45         }
46         abort("Flow control falls after the end of the method")
47     }
48 
49     // returns instruction preceding pushing arguments to the atomic factory
getInitStartnull50     fun getInitStart(stack: Int): AbstractInsnNode {
51         var i = start
52         depth = -stack
53         while (i != null) {
54             executeOne(i, false)
55             if (depth == 0) break
56             i = i.previous
57         }
58         // This may be array initialization in JVM_IR generated bytecode.
59         // Old BE does not empty stack after each array element,
60         // but JVM_IR does, thus, we cannot just assume, that empty stack means initialization start,
61         // instead, we need to find array's ANEWARRAY or NEWARRAY and constant before it.
62         if (i.isArrayStore()) {
63             // Thankfully, in case of nested arrays, JVM_IR puts outer arrays on stack,
64             // So, to support them, we need just to check depth
65             do {
66                 while (i != null && i.opcode != ANEWARRAY && i.opcode != NEWARRAY) {
67                     executeOne(i, false)
68                     i = i.previous
69                 }
70                 if (i == null) break
71                 // Before ANEWARRAY there should be constant integer
72                 executeOne(i, false)
73                 if (depth == 0) break
74                 i = i.previous
75             } while (i != null)
76         }
77         return i ?: abort("Backward flow control falls after the beginning of the method")
78     }
79 
getValueArgInitLastnull80     fun getValueArgInitLast(): AbstractInsnNode {
81         var i = start
82         val valueArgSize = Type.getArgumentTypes((start as MethodInsnNode).desc)[0].size
83         depth = -1
84         while (i != null) {
85             executeOne(i, false)
86             i = i.previous
87             if (depth == -valueArgSize) return i
88         }
89         abort("Backward flow control falls after the beginning of the method")
90     }
91 
AbstractInsnNodenull92     private fun AbstractInsnNode?.isArrayStore(): Boolean = when(this?.opcode) {
93         IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE -> true
94         else -> false
95     }
96 
97     // forward is true when instructions are executed in forward order from top to bottom
executeOnenull98     private fun executeOne(i: AbstractInsnNode, forward: Boolean = true): AbstractInsnNode? {
99         when (i) {
100             is LabelNode -> { /* ignore */ }
101             is LineNumberNode -> { /* ignore */ }
102             is FrameNode -> { /* ignore */ }
103             is MethodInsnNode -> {
104                 popDesc(i.desc, forward)
105                 if (i.opcode == INVOKEVIRTUAL && depth == 0) return i // invoke virtual on atomic field ref
106                 if (i.opcode != INVOKESTATIC) pop(1, forward)
107                 pushDesc(i.desc, forward)
108             }
109             is FieldInsnNode -> when (i.opcode) {
110                 GETSTATIC -> pushDesc(i.desc, forward)
111                 PUTSTATIC -> popDesc(i.desc, forward)
112                 GETFIELD -> {
113                     pop(1, forward)
114                     pushDesc(i.desc, forward)
115                 }
116                 PUTFIELD -> {
117                     popDesc(i.desc, forward)
118                     pop(1, forward)
119                 }
120                 else -> unrecognized(i)
121             }
122             is MultiANewArrayInsnNode -> {
123                 pop(i.dims, forward)
124                 push(1, forward)
125             }
126             is LdcInsnNode -> {
127                 when (i.cst) {
128                     is Double -> push(2, forward)
129                     is Long -> push(2, forward)
130                     else -> push(1, forward)
131                 }
132             }
133             else -> when (i.opcode) {
134                 ASTORE -> {
135                     if (depth == 0) return i // stored atomic field ref
136                     pop(1, forward) // stored something else
137                 }
138                 NOP -> { /* nop */ }
139                 GOTO, TABLESWITCH, LOOKUPSWITCH, ATHROW, IFEQ, IFNE, IFLT, IFGE, IFGT, IFLE, IFNULL, IFNONNULL,
140                 IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ACMPEQ, IF_ACMPNE -> {
141                     abort("Unsupported branching/control within atomic operation")
142                 }
143                 IRETURN, FRETURN, ARETURN, RETURN, LRETURN, DRETURN -> {
144                     abort("Unsupported return within atomic operation")
145                 }
146                 ACONST_NULL -> {
147                     push(1, forward)
148                 }
149                 ICONST_M1, ICONST_0, ICONST_1, ICONST_2, ICONST_3, ICONST_4, ICONST_5, BIPUSH, SIPUSH -> {
150                     push(1, forward)
151                 }
152                 LCONST_0, LCONST_1 -> {
153                     push(2, forward)
154                 }
155                 FCONST_0, FCONST_1, FCONST_2 -> {
156                     push(1, forward)
157                 }
158                 DCONST_0, DCONST_1 -> {
159                     push(2, forward)
160                 }
161                 ILOAD, FLOAD, ALOAD -> {
162                     push(1, forward)
163                 }
164                 LLOAD, DLOAD -> {
165                     push(2, forward)
166                 }
167                 IALOAD, BALOAD, CALOAD, SALOAD -> {
168                     pop(2, forward)
169                     push(1, forward)
170                 }
171                 LALOAD, D2L -> {
172                     pop(2, forward)
173                     push(2, forward)
174                 }
175                 FALOAD -> {
176                     pop(2, forward)
177                     push(1, forward)
178                 }
179                 DALOAD, L2D -> {
180                     pop(2, forward)
181                     push(2, forward)
182                 }
183                 AALOAD -> {
184                     pop(1, forward)
185                     push(1, forward)
186                 }
187                 ISTORE, FSTORE -> {
188                     pop(1, forward)
189                 }
190                 LSTORE, DSTORE -> {
191                     pop(2, forward)
192                 }
193                 IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE -> {
194                     pop(3, forward)
195                 }
196                 LASTORE, DASTORE -> {
197                     pop(4, forward)
198                 }
199                 POP, MONITORENTER, MONITOREXIT -> {
200                     pop(1, forward)
201                 }
202                 POP2 -> {
203                     pop(2, forward)
204                 }
205                 DUP -> {
206                     pop(1, forward)
207                     push(2, forward)
208                 }
209                 DUP_X1 -> {
210                     if (depth <= 1) unsupported()
211                     push(1, forward)
212                 }
213                 DUP_X2 -> {
214                     if (depth <= 2) unsupported()
215                     push(1, forward)
216                 }
217                 DUP2 -> {
218                     pop(2, forward)
219                     push(4, forward)
220                 }
221                 DUP2_X1 -> {
222                     if (depth <= 2) unsupported()
223                     push(2, forward)
224                 }
225                 DUP2_X2 -> {
226                     if (depth <= 3) unsupported()
227                     push(2, forward)
228                 }
229                 SWAP -> {
230                     if (depth <= 1) unsupported()
231                 }
232                 IADD, ISUB, IMUL, IDIV, IREM, IAND, IOR, IXOR, ISHL, ISHR, IUSHR, L2I, D2I, FCMPL, FCMPG -> {
233                     pop(2, forward)
234                     push(1, forward)
235                 }
236                 LADD, LSUB, LMUL, LDIV, LREM, LAND, LOR, LXOR -> {
237                     pop(4, forward)
238                     push(2, forward)
239                 }
240                 FADD, FSUB, FMUL, FDIV, FREM, L2F, D2F -> {
241                     pop(2, forward)
242                     push(1, forward)
243                 }
244                 DADD, DSUB, DMUL, DDIV, DREM -> {
245                     pop(4, forward)
246                     push(2, forward)
247                 }
248                 LSHL, LSHR, LUSHR -> {
249                     pop(3, forward)
250                     push(2, forward)
251                 }
252                 INEG, FNEG, I2B, I2C, I2S, IINC -> {
253                     pop(1, forward)
254                     push(1, forward)
255                 }
256                 LNEG, DNEG -> {
257                     pop(2, forward)
258                     push(2, forward)
259                 }
260                 I2L, F2L -> {
261                     pop(1, forward)
262                     push(2, forward)
263                 }
264                 I2F -> {
265                     pop(1, forward)
266                     push(1, forward)
267                 }
268                 I2D, F2D -> {
269                     pop(1, forward)
270                     push(2, forward)
271                 }
272                 F2I, ARRAYLENGTH, INSTANCEOF -> {
273                     pop(1, forward)
274                     push(1, forward)
275                 }
276                 LCMP, DCMPL, DCMPG -> {
277                     pop(4, forward)
278                     push(1, forward)
279                 }
280                 NEW -> {
281                     push(1, forward)
282                 }
283                 NEWARRAY, ANEWARRAY -> {
284                     pop(1, forward)
285                     push(1, forward)
286                 }
287                 CHECKCAST -> {
288                     /* nop for our needs */
289                 }
290                 else -> unrecognized(i)
291             }
292         }
293         return null
294     }
295 
popDescnull296     private fun popDesc(desc: String, forward: Boolean) {
297         when (desc[0]) {
298             '(' -> {
299                 val types = Type.getArgumentTypes(desc)
300                 pop(types.indices.sumBy { types[it].size }, forward)
301             }
302             'J', 'D' -> pop(2, forward)
303             else -> pop(1, forward)
304         }
305     }
306 
pushDescnull307     private fun pushDesc(desc: String, forward: Boolean) {
308         val index = if (desc[0] == '(') desc.indexOf(')') + 1 else 0
309         when (desc[index]) {
310             'V' -> return
311             'Z', 'C', 'B', 'S', 'I', 'F', '[', 'L' -> {
312                 push(1, forward)
313             }
314             'J', 'D' -> {
315                 push(2, forward)
316             }
317         }
318     }
319 }