• 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     // from putfield/putstatic up to the start of initialisation
getInitStartnull50     fun getInitStart(): AbstractInsnNode {
51         var i = start!!.previous
52         depth = -1
53         while (depth != 0 && i != null) {
54             executeOne(i, false)
55             i = i.previous
56         }
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                 // Before ANEWARRAY there should be constant integer
71                 executeOne(i, false)
72                 i = i?.previous
73             } while (depth != 0 && i != null)
74         }
75 
76         return i
77     }
78 
AbstractInsnNodenull79     private fun AbstractInsnNode?.isArrayStore(): Boolean = when(this?.opcode) {
80         IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE -> true
81         else -> false
82     }
83 
84     // forward is true when instructions are executed in forward order from top to bottom
executeOnenull85     private fun executeOne(i: AbstractInsnNode, forward: Boolean = true): AbstractInsnNode? {
86         when (i) {
87             is LabelNode -> { /* ignore */ }
88             is LineNumberNode -> { /* ignore */ }
89             is FrameNode -> { /* ignore */ }
90             is MethodInsnNode -> {
91                 popDesc(i.desc, forward)
92                 if (i.opcode == INVOKEVIRTUAL && depth == 0) return i // invoke virtual on atomic field ref
93                 if (i.opcode != INVOKESTATIC) pop(1, forward)
94                 pushDesc(i.desc, forward)
95             }
96             is FieldInsnNode -> when (i.opcode) {
97                 GETSTATIC -> pushDesc(i.desc, forward)
98                 PUTSTATIC -> popDesc(i.desc, forward)
99                 GETFIELD -> {
100                     pop(1, forward)
101                     pushDesc(i.desc, forward)
102                 }
103                 PUTFIELD -> {
104                     popDesc(i.desc, forward)
105                     pop(1, forward)
106                 }
107                 else -> unrecognized(i)
108             }
109             is MultiANewArrayInsnNode -> {
110                 pop(i.dims, forward)
111                 push(1, forward)
112             }
113             is LdcInsnNode -> {
114                 when (i.cst) {
115                     is Double -> push(2, forward)
116                     is Long -> push(2, forward)
117                     else -> push(1, forward)
118                 }
119             }
120             else -> when (i.opcode) {
121                 ASTORE -> {
122                     if (depth == 0) return i // stored atomic field ref
123                     pop(1, forward) // stored something else
124                 }
125                 NOP -> { /* nop */ }
126                 GOTO, TABLESWITCH, LOOKUPSWITCH, ATHROW, IFEQ, IFNE, IFLT, IFGE, IFGT, IFLE, IFNULL, IFNONNULL,
127                 IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ACMPEQ, IF_ACMPNE -> {
128                     abort("Unsupported branching/control within atomic operation")
129                 }
130                 IRETURN, FRETURN, ARETURN, RETURN, LRETURN, DRETURN -> {
131                     abort("Unsupported return within atomic operation")
132                 }
133                 ACONST_NULL -> {
134                     push(1, forward)
135                 }
136                 ICONST_M1, ICONST_0, ICONST_1, ICONST_2, ICONST_3, ICONST_4, ICONST_5, BIPUSH, SIPUSH -> {
137                     push(1, forward)
138                 }
139                 LCONST_0, LCONST_1 -> {
140                     push(2, forward)
141                 }
142                 FCONST_0, FCONST_1, FCONST_2 -> {
143                     push(1, forward)
144                 }
145                 DCONST_0, DCONST_1 -> {
146                     push(2, forward)
147                 }
148                 ILOAD, FLOAD, ALOAD -> {
149                     push(1, forward)
150                 }
151                 LLOAD, DLOAD -> {
152                     push(2, forward)
153                 }
154                 IALOAD, BALOAD, CALOAD, SALOAD -> {
155                     pop(2, forward)
156                     push(1, forward)
157                 }
158                 LALOAD, D2L -> {
159                     pop(2, forward)
160                     push(2, forward)
161                 }
162                 FALOAD -> {
163                     pop(2, forward)
164                     push(1, forward)
165                 }
166                 DALOAD, L2D -> {
167                     pop(2, forward)
168                     push(2, forward)
169                 }
170                 AALOAD -> {
171                     pop(1, forward)
172                     push(1, forward)
173                 }
174                 ISTORE, FSTORE -> {
175                     pop(1, forward)
176                 }
177                 LSTORE, DSTORE -> {
178                     pop(2, forward)
179                 }
180                 IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE -> {
181                     pop(3, forward)
182                 }
183                 LASTORE, DASTORE -> {
184                     pop(4, forward)
185                 }
186                 POP, MONITORENTER, MONITOREXIT -> {
187                     pop(1, forward)
188                 }
189                 POP2 -> {
190                     pop(2, forward)
191                 }
192                 DUP -> {
193                     pop(1, forward)
194                     push(2, forward)
195                 }
196                 DUP_X1 -> {
197                     if (depth <= 1) unsupported()
198                     push(1, forward)
199                 }
200                 DUP_X2 -> {
201                     if (depth <= 2) unsupported()
202                     push(1, forward)
203                 }
204                 DUP2 -> {
205                     pop(2, forward)
206                     push(4, forward)
207                 }
208                 DUP2_X1 -> {
209                     if (depth <= 2) unsupported()
210                     push(2, forward)
211                 }
212                 DUP2_X2 -> {
213                     if (depth <= 3) unsupported()
214                     push(2, forward)
215                 }
216                 SWAP -> {
217                     if (depth <= 1) unsupported()
218                 }
219                 IADD, ISUB, IMUL, IDIV, IREM, IAND, IOR, IXOR, ISHL, ISHR, IUSHR, L2I, D2I, FCMPL, FCMPG -> {
220                     pop(2, forward)
221                     push(1, forward)
222                 }
223                 LADD, LSUB, LMUL, LDIV, LREM, LAND, LOR, LXOR -> {
224                     pop(4, forward)
225                     push(2, forward)
226                 }
227                 FADD, FSUB, FMUL, FDIV, FREM, L2F, D2F -> {
228                     pop(2, forward)
229                     push(1, forward)
230                 }
231                 DADD, DSUB, DMUL, DDIV, DREM -> {
232                     pop(4, forward)
233                     push(2, forward)
234                 }
235                 LSHL, LSHR, LUSHR -> {
236                     pop(3, forward)
237                     push(2, forward)
238                 }
239                 INEG, FNEG, I2B, I2C, I2S, IINC -> {
240                     pop(1, forward)
241                     push(1, forward)
242                 }
243                 LNEG, DNEG -> {
244                     pop(2, forward)
245                     push(2, forward)
246                 }
247                 I2L, F2L -> {
248                     pop(1, forward)
249                     push(2, forward)
250                 }
251                 I2F -> {
252                     pop(1, forward)
253                     push(1, forward)
254                 }
255                 I2D, F2D -> {
256                     pop(1, forward)
257                     push(2, forward)
258                 }
259                 F2I, ARRAYLENGTH, INSTANCEOF -> {
260                     pop(1, forward)
261                     push(1, forward)
262                 }
263                 LCMP, DCMPL, DCMPG -> {
264                     pop(4, forward)
265                     push(1, forward)
266                 }
267                 NEW -> {
268                     push(1, forward)
269                 }
270                 NEWARRAY, ANEWARRAY -> {
271                     pop(1, forward)
272                     push(1, forward)
273                 }
274                 CHECKCAST -> {
275                     /* nop for our needs */
276                 }
277                 else -> unrecognized(i)
278             }
279         }
280         return null
281     }
282 
popDescnull283     private fun popDesc(desc: String, forward: Boolean) {
284         when (desc[0]) {
285             '(' -> {
286                 val types = Type.getArgumentTypes(desc)
287                 pop(types.indices.sumBy { types[it].size }, forward)
288             }
289             'J', 'D' -> pop(2, forward)
290             else -> pop(1, forward)
291         }
292     }
293 
pushDescnull294     private fun pushDesc(desc: String, forward: Boolean) {
295         val index = if (desc[0] == '(') desc.indexOf(')') + 1 else 0
296         when (desc[index]) {
297             'V' -> return
298             'Z', 'C', 'B', 'S', 'I', 'F', '[', 'L' -> {
299                 push(1, forward)
300             }
301             'J', 'D' -> {
302                 push(2, forward)
303             }
304         }
305     }
306 }