← Back to branch summary

~ubuntu-branches/debian/sid/scala/sid

« back to all changes in this revision

Viewing changes to src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala

  • Committer: Package Import Robot
  • Author(s): Emmanuel Bourg, Mehdi Dogguy, Lucas Satabin, Frank S. Thomas, Emmanuel Bourg
  • Date: 2015-06-05 23:52:59 UTC
  • mfrom: (1.2.11)
  • Revision ID: package-import@ubuntu.com-20150605235259-wk00vgk83dh8o19g
Tags: 2.10.5-1
http://bugs.debian.org/744278
http://bugs.debian.org/754935
http://bugs.debian.org/724704
* Team upload.

[ Mehdi Dogguy ]
* New upstream release (Closes: #744278).

[ Lucas Satabin ]
* Update patches
* Update the clean target
* Update paths of elements to install
* Update watch file

[ Frank S. Thomas ]
* Remove myself from Uploaders.

[ Emmanuel Bourg ]
* The package has been adopted by the Java Team (Closes: #754935)
* Patched the build to avoid downloading libraries from the Internet
* Replaced the minified JavaScript files with unobfuscated ones
* No longer build scala-partest.jar until diffutils is packaged or replaced
* debian/watch: Fixed the versions matched (x.y.z instead of x.y.z..z)
* debian/rules:
  - Added the missing get-orig-source target (Closes: #724704)
  - Improved the clean target
* debian/control:
  - Build depend on scala (>= 2.10) and bnd
  - Use canonical URLs for the Vcs-* fields
  - Standards-Version updated to 3.9.6 (no changes)
* Switch to debhelper level 9

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
1
1
/* NSC -- new scala compiler
2
 
 * Copyright 2005-2011 LAMP/EPFL
 
2
 * Copyright 2005-2013 LAMP/EPFL
3
3
 * @author  Iulian Dragos
4
4
 */
5
5
 
16
16
  import global._
17
17
  import icodes._
18
18
  import icodes.opcodes._
 
19
  import definitions.RuntimePackage
 
20
 
 
21
  /** The block and index where an instruction is located */
 
22
  type InstrLoc = (BasicBlock, Int)
19
23
 
20
24
  val phaseName = "dce"
21
25
 
36
40
  }
37
41
 
38
42
  /** closures that are instantiated at least once, after dead code elimination */
39
 
  val liveClosures: mutable.Set[Symbol] = new mutable.HashSet()
 
43
  val liveClosures = perRunCaches.newSet[Symbol]()
 
44
 
 
45
  /** closures that are eliminated, populated by GenASM.AsmPhase.run()
 
46
   *  these class symbols won't have a .class physical file, thus shouldn't be included in InnerClasses JVM attribute,
 
47
   *  otherwise some tools get confused or slow (SI-6546)
 
48
   * */
 
49
  val elidedClosures = perRunCaches.newSet[Symbol]()
40
50
 
41
51
  /** Remove dead code.
42
52
   */
43
53
  class DeadCode {
44
54
 
45
55
    def analyzeClass(cls: IClass) {
 
56
      log(s"Analyzing ${cls.methods.size} methods in $cls.")
46
57
      cls.methods.foreach { m =>
47
58
        this.method = m
48
59
        dieCodeDie(m)
53
64
    val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis;
54
65
 
55
66
    /** Use-def chain: give the reaching definitions at the beginning of given instruction. */
56
 
    var defs: immutable.Map[(BasicBlock, Int), immutable.Set[rdef.lattice.Definition]] = immutable.HashMap.empty
 
67
    var defs: immutable.Map[InstrLoc, immutable.Set[rdef.lattice.Definition]] = immutable.HashMap.empty
57
68
 
58
69
    /** Useful instructions which have not been scanned yet. */
59
 
    val worklist: mutable.Set[(BasicBlock, Int)] = new mutable.LinkedHashSet
 
70
    val worklist: mutable.Set[InstrLoc] = new mutable.LinkedHashSet
60
71
 
61
72
    /** what instructions have been marked as useful? */
62
 
    val useful: mutable.Map[BasicBlock, mutable.BitSet] = new mutable.HashMap
 
73
    val useful: mutable.Map[BasicBlock, mutable.BitSet] = perRunCaches.newMap()
63
74
 
64
75
    /** what local variables have been accessed at least once? */
65
76
    var accessedLocals: List[Local] = Nil
66
77
 
 
78
    /** Map from a local and a basic block to the instructions that store to that local in that basic block */
 
79
    val localStores = mutable.Map[(Local, BasicBlock), mutable.BitSet]() withDefault {_ => mutable.BitSet()}
 
80
 
 
81
    /** Stores that clobber previous stores to array or ref locals. See SI-5313 */
 
82
    val clobbers = mutable.Set[InstrLoc]()
 
83
 
67
84
    /** the current method. */
68
85
    var method: IMethod = _
69
86
 
70
87
    /** Map instructions who have a drop on some control path, to that DROP instruction. */
71
 
    val dropOf: mutable.Map[(BasicBlock, Int), (BasicBlock, Int)] = new mutable.HashMap()
 
88
    val dropOf: mutable.Map[InstrLoc, List[InstrLoc]] = perRunCaches.newMap()
72
89
 
73
90
    def dieCodeDie(m: IMethod) {
74
 
      if (m.code ne null) {
75
 
        log("dead code elimination on " + m);
76
 
        dropOf.clear
77
 
        m.code.blocks.clear
 
91
      if (m.hasCode) {
 
92
        debuglog("dead code elimination on " + m);
 
93
        dropOf.clear()
 
94
        localStores.clear()
 
95
        clobbers.clear()
 
96
        m.code.blocks.clear()
78
97
        accessedLocals = m.params.reverse
79
98
        m.code.blocks ++= linearizer.linearize(m)
80
99
        collectRDef(m)
81
 
        mark
 
100
        mark()
82
101
        sweep(m)
83
102
        accessedLocals = accessedLocals.distinct
84
 
        if (m.locals diff accessedLocals nonEmpty) {
85
 
          log("Removed dead locals: " + (m.locals diff accessedLocals))
 
103
        val diff = m.locals diff accessedLocals
 
104
        if (diff.nonEmpty) {
 
105
          val msg = diff.map(_.sym.name)mkString(", ")
 
106
          log(s"Removed ${diff.size} dead locals: $msg")
86
107
          m.locals = accessedLocals.reverse
87
108
        }
88
109
      }
89
110
    }
90
111
 
91
112
    /** collect reaching definitions and initial useful instructions for this method. */
92
 
    def collectRDef(m: IMethod): Unit = if (m.code ne null) {
93
 
      defs = immutable.HashMap.empty; worklist.clear; useful.clear;
 
113
    def collectRDef(m: IMethod): Unit = if (m.hasCode) {
 
114
      defs = immutable.HashMap.empty; worklist.clear(); useful.clear();
94
115
      rdef.init(m);
95
116
      rdef.run;
96
117
 
97
 
      for (bb <- m.code.blocks.toList) {
 
118
      m foreachBlock { bb =>
98
119
        useful(bb) = new mutable.BitSet(bb.size)
99
120
        var rd = rdef.in(bb);
100
121
        for (Pair(i, idx) <- bb.toList.zipWithIndex) {
 
122
 
 
123
          // utility for adding to worklist
 
124
          def moveToWorkList() = moveToWorkListIf(true)
 
125
 
 
126
          // utility for (conditionally) adding to worklist
 
127
          def moveToWorkListIf(cond: Boolean) =
 
128
            if (cond) {
 
129
              debuglog("in worklist:     " + i)
 
130
              worklist += ((bb, idx))
 
131
            } else {
 
132
              debuglog("not in worklist: " + i)
 
133
            }
 
134
 
 
135
          // instruction-specific logic
101
136
          i match {
102
 
            case LOAD_LOCAL(l) =>
 
137
 
 
138
            case LOAD_LOCAL(_) =>
103
139
              defs = defs + Pair(((bb, idx)), rd.vars)
104
 
//              Console.println(i + ": " + (bb, idx) + " rd: " + rd + " and having: " + defs)
 
140
              moveToWorkListIf(false)
 
141
 
 
142
            case STORE_LOCAL(l) =>
 
143
              /* SI-4935 Check whether a module is stack top, if so mark the instruction that loaded it
 
144
               * (otherwise any side-effects of the module's constructor go lost).
 
145
               *   (a) The other two cases where a module's value is stored (STORE_FIELD and STORE_ARRAY_ITEM)
 
146
               *       are already marked (case clause below).
 
147
               *   (b) A CALL_METHOD targeting a method `m1` where the receiver is potentially a module (case clause below)
 
148
               *       will have the module's load marked provided `isSideEffecting(m1)`.
 
149
               *       TODO check for purity (the ICode?) of the module's constructor (besides m1's purity).
 
150
               *       See also https://github.com/paulp/scala/blob/topic/purity-analysis/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
 
151
               */
 
152
              val necessary = rdef.findDefs(bb, idx, 1) exists { p =>
 
153
                val (bb1, idx1) = p
 
154
                bb1(idx1) match {
 
155
                  case LOAD_MODULE(module) => isLoadNeeded(module)
 
156
                  case _                   => false
 
157
                }
 
158
              }
 
159
              moveToWorkListIf(necessary)
 
160
 
 
161
              // add it to the localStores map
 
162
              val key = (l, bb)
 
163
              val set = localStores(key)
 
164
              set += idx
 
165
              localStores(key) = set
 
166
 
105
167
            case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | STORE_FIELD(_, _) |
106
 
                 THROW(_)   | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) | STORE_THIS(_) |
107
 
                 LOAD_EXCEPTION(_) | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() => worklist += ((bb, idx))
108
 
            case CALL_METHOD(m1, _) if isSideEffecting(m1) => worklist += ((bb, idx)); log("marking " + m1)
 
168
                 THROW(_)   | LOAD_ARRAY_ITEM(_) | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) | STORE_THIS(_) |
 
169
                 LOAD_EXCEPTION(_) | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() =>
 
170
              moveToWorkList()
 
171
 
 
172
            case CALL_METHOD(m1, _) if isSideEffecting(m1) =>
 
173
              moveToWorkList()
 
174
 
109
175
            case CALL_METHOD(m1, SuperCall(_)) =>
110
 
              worklist += ((bb, idx)) // super calls to constructor
 
176
              moveToWorkList() // super calls to constructor
 
177
 
111
178
            case DROP(_) =>
112
179
              val necessary = rdef.findDefs(bb, idx, 1) exists { p =>
113
180
                val (bb1, idx1) = p
115
182
                  case CALL_METHOD(m1, _) if isSideEffecting(m1) => true
116
183
                  case LOAD_EXCEPTION(_) | DUP(_) | LOAD_MODULE(_) => true
117
184
                  case _ =>
118
 
                    dropOf((bb1, idx1)) = (bb, idx)
119
 
//                    println("DROP is innessential: " + i + " because of: " + bb1(idx1) + " at " + bb1 + ":" + idx1)
 
185
                    dropOf((bb1, idx1)) = (bb,idx) :: dropOf.getOrElse((bb1, idx1), Nil)
 
186
                    debuglog("DROP is innessential: " + i + " because of: " + bb1(idx1) + " at " + bb1 + ":" + idx1)
120
187
                    false
121
188
                }
122
189
              }
123
 
              if (necessary) worklist += ((bb, idx))
 
190
              moveToWorkListIf(necessary)
124
191
            case _ => ()
 
192
              moveToWorkListIf(false)
125
193
          }
126
194
          rd = rdef.interpret(bb, idx, rd)
127
195
        }
128
196
      }
129
197
    }
130
198
 
 
199
    private def isLoadNeeded(module: Symbol): Boolean = {
 
200
      module.info.member(nme.CONSTRUCTOR).filter(isSideEffecting) != NoSymbol
 
201
    }
 
202
 
131
203
    /** Mark useful instructions. Instructions in the worklist are each inspected and their
132
204
     *  dependencies are marked useful too, and added to the worklist.
133
205
     */
134
206
    def mark() {
135
207
//      log("Starting with worklist: " + worklist)
136
208
      while (!worklist.isEmpty) {
137
 
        val (bb, idx) = worklist.iterator.next
 
209
        val (bb, idx) = worklist.head
138
210
        worklist -= ((bb, idx))
139
 
        if (settings.debug.value)
140
 
          log("Marking instr: \tBB_" + bb + ": " + idx + " " + bb(idx))
 
211
        debuglog("Marking instr: \tBB_" + bb + ": " + idx + " " + bb(idx))
141
212
 
142
213
        val instr = bb(idx)
 
214
        // adds the instrutions that define the stack values about to be consumed to the work list to
 
215
        // be marked useful
 
216
        def addDefs() = for ((bb1, idx1) <- rdef.findDefs(bb, idx, instr.consumed) if !useful(bb1)(idx1)) {
 
217
          debuglog(s"\t${bb1(idx1)} is consumed by $instr")
 
218
          worklist += ((bb1, idx1))
 
219
        }
 
220
 
 
221
        // DROP logic -- if an instruction is useful, its drops are also useful
 
222
        // and we don't mark the DROPs as useful directly but add them to the
 
223
        // worklist so we also mark their reaching defs as useful - see SI-7060
143
224
        if (!useful(bb)(idx)) {
144
225
          useful(bb) += idx
145
 
          dropOf.get(bb, idx) match {
146
 
            case Some((bb1, idx1)) => useful(bb1) += idx1
147
 
            case None => ()
 
226
          dropOf.get(bb, idx) foreach {
 
227
            for ((bb1, idx1) <- _) {
 
228
              /*
 
229
               * SI-7060: A drop that we now mark as useful can be reached via several paths,
 
230
               * so we should follow by marking all its reaching definition as useful too:
 
231
               */
 
232
              debuglog("\tAdding: " + bb1(idx1) + " to the worklist, as a useful DROP.")
 
233
              worklist += ((bb1, idx1))
 
234
            }
148
235
          }
 
236
 
 
237
          // per-instruction logic
149
238
          instr match {
150
239
            case LOAD_LOCAL(l1) =>
151
240
              for ((l2, bb1, idx1) <- defs((bb, idx)) if l1 == l2; if !useful(bb1)(idx1)) {
152
 
                log("\tAdding " + bb1(idx1))
 
241
                debuglog("\tAdding " + bb1(idx1))
153
242
                worklist += ((bb1, idx1))
154
243
              }
155
244
 
 
245
            case STORE_LOCAL(l1) if l1.kind.isRefOrArrayType =>
 
246
              addDefs()
 
247
              // see SI-5313
 
248
              // search for clobbers of this store if we aren't doing l1 = null
 
249
              // this doesn't catch the second store in x=null;l1=x; but in practice this catches
 
250
              // a lot of null stores very cheaply
 
251
              if (idx == 0 || bb(idx - 1) != CONSTANT(Constant(null)))
 
252
                 findClobbers(l1, bb, idx + 1)
 
253
 
156
254
            case nw @ NEW(REFERENCE(sym)) =>
157
255
              assert(nw.init ne null, "null new.init at: " + bb + ": " + idx + "(" + instr + ")")
158
256
              worklist += findInstruction(bb, nw.init)
172
270
              ()
173
271
 
174
272
            case _ =>
175
 
              for ((bb1, idx1) <- rdef.findDefs(bb, idx, instr.consumed) if !useful(bb1)(idx1)) {
176
 
                log("\tAdding " + bb1(idx1))
177
 
                worklist += ((bb1, idx1))
178
 
              }
 
273
              addDefs()
179
274
          }
180
275
        }
181
276
      }
182
277
    }
183
278
 
 
279
    /**
 
280
     * Finds and marks all clobbers of the given local starting in the given
 
281
     * basic block at the given index
 
282
     *
 
283
     * Storing to local variables of reference or array type may be indirectly
 
284
     * observable because it may remove a reference to an object which may allow the object
 
285
     * to be gc'd. See SI-5313. In this code I call the LOCAL_STORE(s) that immediately follow a
 
286
     * LOCAL_STORE and that store to the same local "clobbers." If a LOCAL_STORE is marked
 
287
     * useful then its clobbers must go into the set of clobbers, which will be
 
288
     * compensated for later
 
289
     */
 
290
    def findClobbers(l: Local, bb: BasicBlock, idx: Int) {
 
291
        // previously visited blocks tracked to prevent searching forever in a cycle
 
292
        val inspected = mutable.Set[BasicBlock]()
 
293
        // our worklist of blocks that still need to be checked
 
294
        val blocksToBeInspected = mutable.Set[BasicBlock]()
 
295
 
 
296
        // Tries to find the next clobber of l1 in bb1 starting at idx1.
 
297
        // if it finds one it adds the clobber to clobbers set for later
 
298
        // handling. If not it adds the direct successor blocks to
 
299
        // the uninspectedBlocks to try to find clobbers there. Either way
 
300
        // it adds the exception successor blocks for further search
 
301
        def findClobberInBlock(idx1: Int, bb1: BasicBlock) {
 
302
          val key = ((l, bb1))
 
303
          val foundClobber = (localStores contains key) && {
 
304
            def minIdx(s : mutable.BitSet) = if(s.isEmpty) -1 else s.min
 
305
 
 
306
            // find the smallest index greater than or equal to idx1
 
307
            val clobberIdx = minIdx(localStores(key) dropWhile (_ < idx1))
 
308
            if (clobberIdx == -1)
 
309
              false
 
310
            else {
 
311
              debuglog(s"\t${bb1(clobberIdx)} is a clobber of ${bb(idx)}")
 
312
              clobbers += ((bb1, clobberIdx))
 
313
              true
 
314
            }
 
315
          }
 
316
 
 
317
          // always need to look into the exception successors for additional clobbers
 
318
          // because we don't know when flow might enter an exception handler
 
319
          blocksToBeInspected ++= (bb1.exceptionSuccessors filterNot inspected)
 
320
          // If we didn't find a clobber here then we need to look at successor blocks.
 
321
          // if we found a clobber then we don't need to search in the direct successors
 
322
          if (!foundClobber) {
 
323
            blocksToBeInspected ++= (bb1.directSuccessors filterNot inspected)
 
324
          }
 
325
        }
 
326
 
 
327
        // first search starting at the current index
 
328
        // note we don't put bb in the inspected list yet because a loop may later force
 
329
        // us back around to search from the beginning of bb
 
330
        findClobberInBlock(idx, bb)
 
331
        // then loop until we've exhausted the set of uninspected blocks
 
332
        while(!blocksToBeInspected.isEmpty) {
 
333
          val bb1 = blocksToBeInspected.head
 
334
          blocksToBeInspected -= bb1
 
335
          inspected += bb1
 
336
          findClobberInBlock(0, bb1)
 
337
        }
 
338
    }
 
339
 
184
340
    def sweep(m: IMethod) {
185
341
      val compensations = computeCompensations(m)
186
342
 
187
 
      for (bb <- m.code.blocks.toList) {
188
 
//        Console.println("** Sweeping block " + bb + " **")
 
343
      debuglog("Sweeping: " + m)
 
344
 
 
345
      m foreachBlock { bb =>
 
346
        debuglog(bb + ":")
189
347
        val oldInstr = bb.toList
190
348
        bb.open
191
349
        bb.clear
192
350
        for (Pair(i, idx) <- oldInstr.zipWithIndex) {
193
351
          if (useful(bb)(idx)) {
194
 
//            log(" " + i + " is useful")
 
352
            debuglog(" * " + i + " is useful")
195
353
            bb.emit(i, i.pos)
196
354
            compensations.get(bb, idx) match {
197
355
              case Some(is) => is foreach bb.emit
208
366
          } else {
209
367
            i match {
210
368
              case NEW(REFERENCE(sym)) =>
211
 
                log("skipped object creation: " + sym + "inside " + m)
 
369
                log(s"Eliminated instantation of $sym inside $m")
 
370
              case STORE_LOCAL(l) if clobbers contains ((bb, idx)) =>
 
371
                // if an unused instruction was a clobber of a used store to a reference or array type
 
372
                // then we'll replace it with the store of a null to make sure the reference is
 
373
                // eliminated. See SI-5313
 
374
                bb emit CONSTANT(Constant(null))
 
375
                bb emit STORE_LOCAL(l)
212
376
              case _ => ()
213
377
            }
214
 
            if (settings.debug.value) log("Skipped: bb_" + bb + ": " + idx + "( " + i + ")")
 
378
            debuglog("   " + i + " [swept]")
215
379
          }
216
380
        }
217
381
 
218
382
        if (bb.nonEmpty) bb.close
219
 
        else log("empty block encountered")
 
383
        else log(s"empty block encountered in $m")
220
384
      }
221
385
    }
222
386
 
223
 
    private def computeCompensations(m: IMethod): mutable.Map[(BasicBlock, Int), List[Instruction]] = {
224
 
      val compensations: mutable.Map[(BasicBlock, Int), List[Instruction]] = new mutable.HashMap
 
387
    private def computeCompensations(m: IMethod): mutable.Map[InstrLoc, List[Instruction]] = {
 
388
      val compensations: mutable.Map[InstrLoc, List[Instruction]] = new mutable.HashMap
225
389
 
226
 
      for (bb <- m.code.blocks) {
 
390
      m foreachBlock { bb =>
227
391
        assert(bb.closed, "Open block in computeCompensations")
228
 
        for ((i, idx) <- bb.toList.zipWithIndex) {
 
392
        foreachWithIndex(bb.toList) { (i, idx) =>
229
393
          if (!useful(bb)(idx)) {
230
 
            for ((consumedType, depth) <- i.consumedTypes.reverse.zipWithIndex) {
231
 
              log("Finding definitions of: " + i + "\n\t" + consumedType + " at depth: " + depth)
 
394
            foreachWithIndex(i.consumedTypes.reverse) { (consumedType, depth) =>
 
395
              debuglog("Finding definitions of: " + i + "\n\t" + consumedType + " at depth: " + depth)
232
396
              val defs = rdef.findDefs(bb, idx, 1, depth)
233
397
              for (d <- defs) {
234
398
                val (bb, idx) = d
 
399
                debuglog("rdef: "+ bb(idx))
235
400
                bb(idx) match {
236
401
                  case DUP(_) if idx > 0 =>
237
402
                    bb(idx - 1) match {
260
425
      res
261
426
    }
262
427
 
263
 
    private def findInstruction(bb: BasicBlock, i: Instruction): (BasicBlock, Int) = {
 
428
    private def findInstruction(bb: BasicBlock, i: Instruction): InstrLoc = {
264
429
      for (b <- linearizer.linearizeAt(method, bb)) {
265
430
        val idx = b.toList indexWhere (_ eq i)
266
431
        if (idx != -1)
269
434
      abort("could not find init in: " + method)
270
435
    }
271
436
 
 
437
    private def isPure(sym: Symbol) = (
 
438
         (sym.isGetter && sym.isEffectivelyFinal && !sym.isLazy)
 
439
      || (sym.isPrimaryConstructor && (sym.enclosingPackage == RuntimePackage || inliner.isClosureClass(sym.owner)))
 
440
    )
272
441
    /** Is 'sym' a side-effecting method? TODO: proper analysis.  */
273
 
    private def isSideEffecting(sym: Symbol): Boolean = {
274
 
      !((sym.isGetter && sym.isFinal && !sym.isLazy)
275
 
       || (sym.isConstructor
276
 
           && !(sym.owner == method.symbol.owner && method.symbol.isConstructor) // a call to another constructor
277
 
           && sym.owner.owner == definitions.RuntimePackage.moduleClass)
278
 
       || (sym.isConstructor && inliner.isClosureClass(sym.owner))
279
 
/*       || definitions.isBox(sym)
280
 
       || definitions.isUnbox(sym)*/)
281
 
    }
 
442
    private def isSideEffecting(sym: Symbol) = !isPure(sym)
 
443
 
282
444
  } /* DeadCode */
283
445
}