[turbofan] Implement jump threading after register allocation.

src/compiler/instruction.h

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_COMPILER_INSTRUCTION_H_
 #define V8_COMPILER_INSTRUCTION_H_
 
 #include <deque>
 #include <iosfwd>
 #include <map>
@@ skipping 423 matching lines @@
   }
 
   bool HasOutput() const { return OutputCount() == 1; }
   InstructionOperand* Output() const { return OutputAt(0); }
 
   size_t InputCount() const { return InputCountField::decode(bit_field_); }
   InstructionOperand* InputAt(size_t i) const {
     DCHECK(i < InputCount());
     return operands_[OutputCount() + i];
   }
+  void SetInputAt(size_t i, InstructionOperand* operand) {
+    DCHECK(i < InputCount());
+    operands_[OutputCount() + i] = operand;
+  }
 
   size_t TempCount() const { return TempCountField::decode(bit_field_); }
   InstructionOperand* TempAt(size_t i) const {
     DCHECK(i < TempCount());
     return operands_[OutputCount() + InputCount() + i];
   }
 
   InstructionCode opcode() const { return opcode_; }
   ArchOpcode arch_opcode() const { return ArchOpcodeField::decode(opcode()); }
   AddressingMode addressing_mode() const {
@@ skipping 59 matching lines @@
     DCHECK_EQ(NULL, pointer_map_);
     pointer_map_ = map;
   }
 
   // Placement new operator so that we can smash instructions into
   // zone-allocated memory.
   void* operator new(size_t, void* location) { return location; }
 
   void operator delete(void* pointer, void* location) { UNREACHABLE(); }
 
+  void OverwriteWithNop() {
+    opcode_ = ArchOpcodeField::encode(kArchNop);
+    bit_field_ = 0;
+    pointer_map_ = NULL;
+  }
+
+  bool IsNop() const {
+    return arch_opcode() == kArchNop && InputCount() == 0 &&
+           OutputCount() == 0 && TempCount() == 0;
+  }
+
  protected:
   explicit Instruction(InstructionCode opcode)
       : opcode_(opcode),
         bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) |
                    TempCountField::encode(0) | IsCallField::encode(false) |
                    IsControlField::encode(false)),
         pointer_map_(NULL) {}
 
   Instruction(InstructionCode opcode, size_t output_count,
               InstructionOperand** outputs, size_t input_count,
@@ skipping 59 matching lines @@
   }
 
   ParallelMove* GetParallelMove(InnerPosition pos) {
     return parallel_moves_[pos];
   }
 
   const ParallelMove* GetParallelMove(InnerPosition pos) const {
     return parallel_moves_[pos];
   }
 
+  bool IsRedundant() const;
+
   static GapInstruction* New(Zone* zone) {
     void* buffer = zone->New(sizeof(GapInstruction));
     return new (buffer) GapInstruction(kGapInstruction);
   }
 
   static GapInstruction* cast(Instruction* instr) {
     DCHECK(instr->IsGapMoves());
     return static_cast<GapInstruction*>(instr);
   }
 
@@ skipping 274 matching lines @@
 
   typedef ZoneVector<BasicBlock::RpoNumber> Successors;
   Successors& successors() { return successors_; }
   const Successors& successors() const { return successors_; }
   size_t SuccessorCount() const { return successors_.size(); }
 
   typedef ZoneVector<PhiInstruction*> PhiInstructions;
   const PhiInstructions& phis() const { return phis_; }
   void AddPhi(PhiInstruction* phi) { phis_.push_back(phi); }
 
+  void set_ao_number(BasicBlock::RpoNumber ao_number) {
+    ao_number_ = ao_number;
+  }
+
  private:
   Successors successors_;
   Predecessors predecessors_;
   PhiInstructions phis_;
   const BasicBlock::Id id_;
-  const BasicBlock::RpoNumber ao_number_;  // Assembly order number.
+  BasicBlock::RpoNumber ao_number_;  // Assembly order number.
   const BasicBlock::RpoNumber rpo_number_;
   const BasicBlock::RpoNumber loop_header_;
   const BasicBlock::RpoNumber loop_end_;
   int32_t code_start_;   // start index of arch-specific code.
   int32_t code_end_;     // end index of arch-specific code.
   const bool deferred_;  // Block contains deferred code.
 };
 
 typedef ZoneDeque<Constant> ConstantDeque;
 typedef std::map<int, Constant, std::less<int>,
@@ skipping 72 matching lines @@
   Isolate* isolate() const { return zone()->isolate(); }
   const PointerMapDeque* pointer_maps() const { return &pointer_maps_; }
   Zone* zone() const { return zone_; }
 
   // Used by the instruction selector while adding instructions.
   int AddInstruction(Instruction* instr);
   void StartBlock(BasicBlock::RpoNumber rpo);
   void EndBlock(BasicBlock::RpoNumber rpo);
 
   int AddConstant(int virtual_register, Constant constant) {
+    // TODO(titzer): allow RPO numbers as constants?
+    DCHECK(constant.type() != Constant::kRpoNumber);
     DCHECK(virtual_register >= 0 && virtual_register < next_virtual_register_);
     DCHECK(constants_.find(virtual_register) == constants_.end());
     constants_.insert(std::make_pair(virtual_register, constant));
     return virtual_register;
   }
   Constant GetConstant(int virtual_register) const {
     ConstantMap::const_iterator it = constants_.find(virtual_register);
     DCHECK(it != constants_.end());
     DCHECK_EQ(virtual_register, it->first);
     return it->second;
   }
 
-  typedef ConstantDeque Immediates;
-  const Immediates& immediates() const { return immediates_; }
+  typedef ZoneVector<Constant> Immediates;
+  Immediates& immediates() { return immediates_; }
 
   int AddImmediate(Constant constant) {
     int index = static_cast<int>(immediates_.size());
     immediates_.push_back(constant);
     return index;
   }
   Constant GetImmediate(int index) const {
     DCHECK(index >= 0);
     DCHECK(index < static_cast<int>(immediates_.size()));
     return immediates_[index];
   }
 
   class StateId {
    public:
     static StateId FromInt(int id) { return StateId(id); }
     int ToInt() const { return id_; }
 
    private:
     explicit StateId(int id) : id_(id) {}
     int id_;
   };
 
   StateId AddFrameStateDescriptor(FrameStateDescriptor* descriptor);
   FrameStateDescriptor* GetFrameStateDescriptor(StateId deoptimization_id);
   int GetFrameStateDescriptorCount();
 
+  BasicBlock::RpoNumber InputRpo(Instruction* instr, size_t index) {
+    InstructionOperand* operand = instr->InputAt(index);
+    Constant constant = operand->IsImmediate() ? GetImmediate(operand->index())
+                                               : GetConstant(operand->index());
+    return constant.ToRpoNumber();
+  }
+
  private:
   friend std::ostream& operator<<(std::ostream& os,
                                   const PrintableInstructionSequence& code);
 
   typedef std::set<int, std::less<int>, ZoneIntAllocator> VirtualRegisterSet;
 
   Zone* const zone_;
   InstructionBlocks* const instruction_blocks_;
   IntVector block_starts_;
   ConstantMap constants_;
-  ConstantDeque immediates_;
+  Immediates immediates_;
   InstructionDeque instructions_;
   int next_virtual_register_;
   PointerMapDeque pointer_maps_;
   VirtualRegisterSet doubles_;
   VirtualRegisterSet references_;
   DeoptimizationVector deoptimization_entries_;
 
   DISALLOW_COPY_AND_ASSIGN(InstructionSequence);
 };
 
 
 struct PrintableInstructionSequence {
   const RegisterConfiguration* register_configuration_;
   const InstructionSequence* sequence_;
 };
 
 
 std::ostream& operator<<(std::ostream& os,
                          const PrintableInstructionSequence& code);
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_INSTRUCTION_H_