Implement simple spill store elimination.

runtime/vm/flow_graph_allocator.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_FLOW_GRAPH_ALLOCATOR_H_
 #define VM_FLOW_GRAPH_ALLOCATOR_H_
 
 #include "vm/growable_array.h"
 #include "vm/intermediate_language.h"
 
@@ skipping 58 matching lines @@
   // required to resolve data flow between split siblings when allocation
   // is finished.
   // For specific examples see comments inside ProcessOneInstruction.
   // Additionally creates parallel moves at the joins' predecessors
   // that will be used for phi resolution.
   void NumberInstructions();
   Instruction* InstructionAt(intptr_t pos) const;
   bool IsBlockEntry(intptr_t pos) const;
 
   LiveRange* GetLiveRange(intptr_t vreg);
+  LiveRange* MakeLiveRangeForTemporary();
 
   // Visit instructions in the postorder and build live ranges for
   // all SSA values.
   void BuildLiveRanges();
   Instruction* ConnectOutgoingPhiMoves(BlockEntryInstr* block);
   void ProcessOneInstruction(BlockEntryInstr* block, Instruction* instr);
   void ConnectIncomingPhiMoves(BlockEntryInstr* block);
   void BlockLocation(Location loc, intptr_t pos);
 
   // Process live ranges sorted by their start and assign registers
   // to them
   void AllocateCPURegisters();
   void AdvanceActiveIntervals(const intptr_t start);
 
   // Connect split siblings over non-linear control flow edges.
   void ResolveControlFlow();
   void ConnectSplitSiblings(LiveRange* range,
                             BlockEntryInstr* source_block,
                             BlockEntryInstr* target_block);
 
 
   // Update location slot corresponding to the use with location allocated for
   // the use's live range.
   void ConvertUseTo(UsePosition* use, Location loc);
   void ConvertAllUses(LiveRange* range);
 
   // Add live range to the list of unallocated live ranges to be processed
   // by the allocator.
   void AddToUnallocated(LiveRange* range);
-#ifdef DEBUG
+#if defined(DEBUG)
   bool UnallocatedIsSorted();
 #endif
 
   // Try to find a free register for an unallocated live range.
   bool AllocateFreeRegister(LiveRange* unallocated);
 
   // Try to find a register that can be used by a given live range.
   // If all registers are occupied consider evicting interference for
   // a register that is going to be used as far from the start of
   // the unallocated live range as possible.
@@ skipping 14 matching lines @@
 
   bool UpdateFreeUntil(Register reg,
                        LiveRange* unallocated,
                        intptr_t* cur_free_until,
                        intptr_t* cur_blocked_at);
 
   // Split given live range in an optimal position between given positions.
   LiveRange* SplitBetween(LiveRange* range, intptr_t from, intptr_t to);
 
   // Find a spill slot that can be used by the given live range.
-  intptr_t AllocateSpillSlotFor(LiveRange* range);
+  void AllocateSpillSlotFor(LiveRange* range);
 
   // Allocate the given live range to a spill slot.
   void Spill(LiveRange* range);
 
   // Spill the given live range from the given position onwards.
   void SpillAfter(LiveRange* range, intptr_t from);
 
   // Spill the given live range from the given position until some
   // position preceeding the to position.
   void SpillBetween(LiveRange* range, intptr_t from, intptr_t to);
@@ skipping 29 matching lines @@
   // SSA values.
   const intptr_t vreg_count_;
 
   // LiveRanges corresponding to SSA values.
   GrowableArray<LiveRange*> live_ranges_;
 
   // Worklist for register allocator. Always maintained sorted according
   // to ShouldBeAllocatedBefore predicate.
   GrowableArray<LiveRange*> unallocated_;
 
+#if defined(DEBUG)
+  GrowableArray<LiveRange*> temporaries_;
+#endif
+
+  GrowableArray<LiveRange*> spilled_;
+
   // Per register lists of allocated live ranges.  Contain only those
   // ranges that can be affected by future allocation decisions.
   // Those live ranges that end before the start of the current live range are
   // removed from the list and will not be affected.
   GrowableArray<LiveRange*> cpu_regs_[kNumberOfCpuRegisters];
 
   // List of used spill slots. Contain positions after which spill slots
   // become free and can be reused for allocation.
   GrowableArray<intptr_t> spill_slots_;
 
@@ skipping 111 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(AllocationFinger);
 };
 
 
 // LiveRange represents a sequence of UseIntervals for a given SSA value.
 class LiveRange : public ZoneAllocated {
  public:
   explicit LiveRange(intptr_t vreg)
     : vreg_(vreg),
       assigned_location_(),
+      spill_slot_(),
       uses_(NULL),
       first_use_interval_(NULL),
       last_use_interval_(NULL),
       next_sibling_(NULL),
       finger_() {
   }
 
   static LiveRange* MakeTemp(intptr_t pos, Location* location_slot);
 
   intptr_t vreg() const { return vreg_; }
   LiveRange* next_sibling() const { return next_sibling_; }
   UsePosition* first_use() const { return uses_; }
   void set_first_use(UsePosition* use) { uses_ = use; }
   UseInterval* first_use_interval() const { return first_use_interval_; }
   UseInterval* last_use_interval() const { return last_use_interval_; }
   Location assigned_location() const { return assigned_location_; }
   intptr_t Start() const { return first_use_interval()->start(); }
   intptr_t End() const { return last_use_interval()->end(); }
 
   AllocationFinger* finger() { return &finger_; }
 
   void set_assigned_location(Location location) {
     assigned_location_ = location;
   }
 
+  void set_spill_slot(Location spill_slot) {
+    spill_slot_ = spill_slot;
+  }
+
   void DefineAt(intptr_t pos);
 
   void AddUse(intptr_t pos, Location* location_slot);
   void AddUseInterval(intptr_t start, intptr_t end);
 
   void Print();
 
   void AssignLocation(UseInterval* use, Location loc);
 
   LiveRange* SplitAt(intptr_t pos);
 
   bool CanCover(intptr_t pos) const {
     return (Start() <= pos) && (pos < End());
   }
 
+  Location spill_slot() const {
+    return spill_slot_;
+  }
+
  private:
   LiveRange(intptr_t vreg,
             UsePosition* uses,
             UseInterval* first_use_interval,
             UseInterval* last_use_interval,
             LiveRange* next_sibling)
     : vreg_(vreg),
       assigned_location_(),
       uses_(uses),
       first_use_interval_(first_use_interval),
       last_use_interval_(last_use_interval),
       next_sibling_(next_sibling),
       finger_() {
   }
 
   const intptr_t vreg_;
   Location assigned_location_;
+  Location spill_slot_;
 
   UsePosition* uses_;
   UseInterval* first_use_interval_;
   UseInterval* last_use_interval_;
 
   LiveRange* next_sibling_;
 
   AllocationFinger finger_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_ALLOCATOR_H_