1804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray/* 2804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * 4804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * you may not use this file except in compliance with the License. 6804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * You may obtain a copy of the License at 7804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * 8804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * 10804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * See the License for the specific language governing permissions and 14804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray * limitations under the License. 15804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray */ 16804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 17fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell#include "arch/x86/instruction_set_features_x86.h" 18b666f4805c8ae707ea6fd7f6c7f375e0b000dba8Mathieu Chartier#include "base/arena_allocator.h" 19804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "builder.h" 2031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray#include "code_generator.h" 218a16d97fb8f031822b206e65f9109a071da40563Nicolas Geoffray#include "code_generator_x86.h" 22804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "dex_file.h" 23804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "dex_instruction.h" 24cd6dffedf1bd8e6dfb3fb0c933551f9a90f7de3fCalin Juravle#include "driver/compiler_options.h" 25804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "nodes.h" 26804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "optimizing_unit_test.h" 27360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray#include "prepare_for_register_allocation.h" 28804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "ssa_liveness_analysis.h" 29804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 30804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray#include "gtest/gtest.h" 31804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 32804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffraynamespace art { 33804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 3426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffraystatic void DumpBitVector(BitVector* vector, 3526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray std::ostream& buffer, 3626066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray size_t count, 3726066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray const char* prefix) { 3826066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray buffer << prefix; 3926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray buffer << '('; 4026066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray for (size_t i = 0; i < count; ++i) { 4126066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray buffer << vector->IsBitSet(i); 4226066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray } 4326066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray buffer << ")\n"; 4426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray} 4526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray 46804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffraystatic void TestCode(const uint16_t* data, const char* expected) { 47804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray ArenaPool pool; 48804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray ArenaAllocator allocator(&pool); 490a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HGraph* graph = CreateGraph(&allocator); 505e8b137d28c840b128e2488f954cccee3e86db14David Brazdil HGraphBuilder builder(graph); 51804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); 525e8b137d28c840b128e2488f954cccee3e86db14David Brazdil bool graph_built = builder.BuildGraph(*item); 535e8b137d28c840b128e2488f954cccee3e86db14David Brazdil ASSERT_TRUE(graph_built); 54e53798a7e3267305f696bf658e418c92e63e0834Nicolas Geoffray graph->TryBuildingSsa(); 55360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // `Inline` conditions into ifs. 56360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray PrepareForRegisterAllocation(graph).Run(); 57fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell std::unique_ptr<const X86InstructionSetFeatures> features_x86( 58fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell X86InstructionSetFeatures::FromCppDefines()); 59fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 600d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray SsaLivenessAnalysis liveness(graph, &codegen); 61804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray liveness.Analyze(); 62804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 63804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray std::ostringstream buffer; 64804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) { 65804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray HBasicBlock* block = it.Current(); 66804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray buffer << "Block " << block->GetBlockId() << std::endl; 6726066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray size_t ssa_values = liveness.GetNumberOfSsaValues(); 68804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray BitVector* live_in = liveness.GetLiveInSet(*block); 6926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray DumpBitVector(live_in, buffer, ssa_values, " live in: "); 70804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray BitVector* live_out = liveness.GetLiveOutSet(*block); 7126066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray DumpBitVector(live_out, buffer, ssa_values, " live out: "); 72804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray BitVector* kill = liveness.GetKillSet(*block); 7326066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray DumpBitVector(kill, buffer, ssa_values, " kill: "); 74804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 75804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray ASSERT_STREQ(expected, buffer.str().c_str()); 76804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 77804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 78804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, CFG1) { 79804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 80804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 8131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live in: (0)\n" 8231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live out: (0)\n" 8331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " kill: (1)\n" 84804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 8531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live in: (0)\n" 8631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live out: (0)\n" 8731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " kill: (0)\n" 88804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" 8931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live in: (0)\n" 9031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live out: (0)\n" 9131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " kill: (0)\n"; 92804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 93804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Constant is not used. 94804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 95804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 96804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN_VOID); 97804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 98804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 99804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 100804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 101804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, CFG2) { 102804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 103804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 10426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (0)\n" 10526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (1)\n" 10626066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (1)\n" 107804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 10826066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (1)\n" 10926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (0)\n" 11026066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (0)\n" 111804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" 11226066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (0)\n" 11326066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (0)\n" 11426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (0)\n"; 115804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 116804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 117804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 118804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN); 119804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 120804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 121804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 122804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 123804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, CFG3) { 124804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 125804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 12626066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (000)\n" 12726066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (110)\n" 12826066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (110)\n" 129804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // block with add 13026066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (110)\n" 13126066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (001)\n" 13226066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (001)\n" 133804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // block with return 13426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (001)\n" 13526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (000)\n" 13626066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (000)\n" 137804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // exit block 13826066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (000)\n" 13926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (000)\n" 14026066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (000)\n"; 141804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 142804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 143804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 3 << 12 | 0, 144804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 1 << 8, 145804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::ADD_INT_2ADDR | 1 << 12, 146804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x100, 147804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN); 148804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 149804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 150804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 151804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 152804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, CFG4) { 153804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a; 154804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // if (0 == 0) { 155804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 5; 156804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } else { 157804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 158804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 159804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return a; 160804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // 161804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 162e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, constant5, phi) 163804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 164804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 165e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 166e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (1110)\n" 167e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (1110)\n" 168804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // block with if 169e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (1110)\n" 170e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 171e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 172804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // else block 173e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0100)\n" 174e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 175e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 176804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // then block 177e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0010)\n" 178e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 179e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 180804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // return block 181e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 182e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 183e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0001)\n" 184804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // exit block 185e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 186e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 187e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n"; 188804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 189804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 190804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 191804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 192804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 193804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x200, 194804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 195804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 196804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 197804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 198804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 199804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 200804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, CFG5) { 201804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 202804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // if (0 == 0) { 203804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } else { 204804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 205804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 206804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return a; 207e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // 208e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // Bitsets are made of: 209e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, phi) 210804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 211804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 212e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 213e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 214e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (110)\n" 215804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // block with if 216e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 217e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 218e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 219804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // else block 220e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 221e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 222e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 223804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // return block 224e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 225e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 226e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (001)\n" 227804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // exit block 228e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 229e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 230e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 231622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray "Block 5\n" // block to avoid critical edge. Predecessor is 1, successor is 3. 232e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (100)\n" 233e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 234e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n"; 235804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 236804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 237804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 238804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 3, 239804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 240804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 241804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 242804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 243804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 244804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 245804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, Loop1) { 246804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Simple loop with one preheader and one back edge. 247804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 248804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // while (a == a) { 249804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 250804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 251804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return; 252e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // Bitsets are made of: 253e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, phi) 254804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 255804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 256e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 257e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 258e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (110)\n" 259804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // pre header 260e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 261e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 262e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 263804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 264e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 265e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 266e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (001)\n" 267804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // back edge 268e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 269e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 270e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 271804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // return block 272e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 273e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 274e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 275804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // exit block 276e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 277e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 278e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n"; 279804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 280804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 281804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 282804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 283804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 284804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 285804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFD00, 286804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN_VOID); 287804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 288804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 289804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 290804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 291804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, Loop3) { 292804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Test that the returned value stays live in a preceding loop. 293804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 294804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // while (a == a) { 295804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 296804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 297804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return 5; 298e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // Bitsets are made of: 299e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, constant5, phi) 300804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 301804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 302e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 303e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (1110)\n" 304e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (1110)\n" 305804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 306e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (1110)\n" 307e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 308e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 309804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 310e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0110)\n" 311e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 312e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0001)\n" 313804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // back edge 314e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0110)\n" 315e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 316e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 317804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // return block 318e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0010)\n" 319e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 320e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 321804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // exit block 322e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 323e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 324e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n"; 325804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 326804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 327804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 328804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 329804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 330804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFD00, 331804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 1 << 8, 332804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 1 << 8); 333804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 334804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 335804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 336804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 337804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 338804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, Loop4) { 339804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Make sure we support a preheader of a loop not being the first predecessor 340804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // in the predecessor list of the header. 341804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 342804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // while (a == a) { 343804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 344804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 345804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return a; 346804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 347e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, phi) 348804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 349804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 350e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 351e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 352e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (110)\n" 353804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 354e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 355e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 356e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 357804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 358e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 359e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (011)\n" 360e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (001)\n" 361804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // back edge 362e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 363e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 364e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 365804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // pre loop header 366e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 367e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 368e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 369804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // return block 370e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (001)\n" 371e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 372e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 373804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // exit block 374e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 375e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 376e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n"; 377804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 378804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 379804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 380804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x500, 381804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 5, 382804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 383804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFD00, 384804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFC00, 385804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 386804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 387804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 388804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 389804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 390804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, Loop5) { 391804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Make sure we create a preheader of a loop when a header originally has two 392804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // incoming blocks and one back edge. 393804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 3943afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray // (constant0, constant4, constant5, phi in block 8) 395804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 396804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 3973afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0000)\n" 3983afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (1110)\n" 3993afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (1110)\n" 400804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 4013afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (1110)\n" 4023afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0110)\n" 4033afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 404804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" 4053afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0100)\n" 4063afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4073afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 408804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" 4093afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0010)\n" 4103afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4113afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 412804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // loop header 4133afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0001)\n" 4143afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0001)\n" 4153afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 416804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // back edge 4173afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0001)\n" 4183afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0001)\n" 4193afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 420804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // return block 4213afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0001)\n" 4223afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4233afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 424804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 7\n" // exit block 4253afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0000)\n" 4263afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4273afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 428804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 8\n" // synthesized pre header 4293afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0000)\n" 4303afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0001)\n" 4313afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0001)\n"; 432804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 433804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 434804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 435804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 436804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 437804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x200, 438804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 439804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 3, 440804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFE00, 441804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 442804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 443804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 444804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 445804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 446804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, Loop6) { 447804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 448db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray // (constant0, constant4, constant5, phi in block 2) 449804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 450804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 451db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0000)\n" 452db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (1110)\n" 453db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (1110)\n" 454804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 455db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (1110)\n" 456db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 457db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 458804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 459db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 460db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0111)\n" 461db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0001)\n" 462804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" 463db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 464db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 465db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 466db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray "Block 4\n" // back edge 467db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 468db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 469db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 470db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray "Block 5\n" // back edge 471db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 472db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 473db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 474804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // return block 475db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0001)\n" 476db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0000)\n" 477db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 478804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 7\n" // exit block 479db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0000)\n" 480db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0000)\n" 481db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n"; 482804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 483804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 484804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 485804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 8, 486804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 487804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 488804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 489804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFA00, 490804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xF900, 491804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 492804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 493804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 494804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 495804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 496804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 497804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas GeoffrayTEST(LivenessTest, Loop7) { 498804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 499e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, constant5, phi in block 2, phi in block 6) 500804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 501804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 502e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00000)\n" 503e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (11100)\n" 504e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (11100)\n" 505804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 506e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (11100)\n" 507e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01100)\n" 508e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 509804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 510e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (01100)\n" 511e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01110)\n" 512e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00010)\n" 513804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" 514e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (01100)\n" 515e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01100)\n" 516e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 517804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // loop exit 518e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00100)\n" 519e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 520e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 521804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // back edge 522e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (01100)\n" 523e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01100)\n" 524e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 525804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // return block 526e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00000)\n" 527e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 528e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00001)\n" 529804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 7\n" // exit block 530e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00000)\n" 531e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 532e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 533622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray "Block 8\n" // synthesized block to avoid critical edge. 534e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00010)\n" 535e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 536e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n"; 537804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 538804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 539804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 540804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 8, 541804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 542804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 543804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 544804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x0200, 545804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xF900, 546804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 547804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 548804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 549804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 550804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 5518ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas GeoffrayTEST(LivenessTest, Loop8) { 5528ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // var a = 0; 5538ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // while (a == a) { 5548ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // a = a + a; 5558ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // } 5568ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // return a; 5578ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // 5588ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // We want to test that the ins of the loop exit 5598ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // does contain the phi. 5608ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // Bitsets are made of: 5618ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // (constant0, phi, add) 5628ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray const char* expected = 5638ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 0\n" 5648ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (000)\n" 5658ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (100)\n" 5668ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (100)\n" 5678ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 1\n" // pre loop header 5688ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (100)\n" 5698ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5708ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (000)\n" 5718ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 2\n" // loop header 5728ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (000)\n" 5738ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (010)\n" 5748ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (010)\n" 5758ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 3\n" // back edge 5768ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (010)\n" 5778ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5788ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (001)\n" 5798ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 4\n" // return block 5808ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (010)\n" 5818ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5828ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (000)\n" 5838ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 5\n" // exit block 5848ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (000)\n" 5858ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5868ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (000)\n"; 5878ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 5888ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 5898ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::CONST_4 | 0 | 0, 5908ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::IF_EQ, 6, 5918ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::ADD_INT, 0, 0, 5928ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::GOTO | 0xFB00, 5938ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::RETURN | 0 << 8); 5948ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 5958ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray TestCode(data, expected); 5968ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray} 5978ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 598804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} // namespace art 599