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 3068289a531484d26214e09f1eadd9833531a3bc3cAlex Lightnamespace art { 31d9510dfc32349eeb4f2145c801f7ba1d5bccfb12David Brazdil 324833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilclass LivenessTest : public CommonCompilerTest {}; 334833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 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); 49badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil HGraph* graph = CreateCFG(&allocator, data); 50360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // `Inline` conditions into ifs. 51360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray PrepareForRegisterAllocation(graph).Run(); 52fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell std::unique_ptr<const X86InstructionSetFeatures> features_x86( 53fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell X86InstructionSetFeatures::FromCppDefines()); 54fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 550d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray SsaLivenessAnalysis liveness(graph, &codegen); 56804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray liveness.Analyze(); 57804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 58804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray std::ostringstream buffer; 59804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) { 60804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray HBasicBlock* block = it.Current(); 61804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray buffer << "Block " << block->GetBlockId() << std::endl; 6226066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray size_t ssa_values = liveness.GetNumberOfSsaValues(); 63804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray BitVector* live_in = liveness.GetLiveInSet(*block); 6426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray DumpBitVector(live_in, buffer, ssa_values, " live in: "); 65804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray BitVector* live_out = liveness.GetLiveOutSet(*block); 6626066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray DumpBitVector(live_out, buffer, ssa_values, " live out: "); 67804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray BitVector* kill = liveness.GetKillSet(*block); 6826066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray DumpBitVector(kill, buffer, ssa_values, " kill: "); 69804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 70804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray ASSERT_STREQ(expected, buffer.str().c_str()); 71804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 72804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 734833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, CFG1) { 74804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 75804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 7631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live in: (0)\n" 7731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live out: (0)\n" 7831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " kill: (1)\n" 79804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 8031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live in: (0)\n" 8131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live out: (0)\n" 8231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " kill: (0)\n" 83804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" 8431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live in: (0)\n" 8531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " live out: (0)\n" 8631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray " kill: (0)\n"; 87804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 88804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Constant is not used. 89804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 90804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 91804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN_VOID); 92804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 93804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 94804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 95804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 964833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, CFG2) { 97804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 98804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 9926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (0)\n" 10026066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (1)\n" 10126066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (1)\n" 102804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 10326066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (1)\n" 10426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (0)\n" 10526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (0)\n" 106804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" 10726066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (0)\n" 10826066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (0)\n" 10926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (0)\n"; 110804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 111804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 112804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 113804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN); 114804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 115804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 116804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 117804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 1184833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, CFG3) { 119804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 120804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 12126066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (000)\n" 12226066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (110)\n" 12326066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (110)\n" 124804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // block with add 12526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (110)\n" 12626066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (001)\n" 12726066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (001)\n" 128804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // block with return 12926066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (001)\n" 13026066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (000)\n" 13126066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (000)\n" 132804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // exit block 13326066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live in: (000)\n" 13426066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " live out: (000)\n" 13526066f20570a589fb256ccaf0f3f5e11c2e10457Nicolas Geoffray " kill: (000)\n"; 136804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 137804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 138804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 3 << 12 | 0, 139804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 1 << 8, 140804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::ADD_INT_2ADDR | 1 << 12, 141804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x100, 142804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN); 143804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 144804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 145804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 146804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 1474833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, CFG4) { 148804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a; 149804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // if (0 == 0) { 150804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 5; 151804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } else { 152804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 153804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 154804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return a; 155804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // 156804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 157dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // (constant0, constant5, constant4, phi) 158804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 159804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 160e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 161e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (1110)\n" 162e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (1110)\n" 163804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // block with if 164e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (1110)\n" 165e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 166e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 167804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // else block 168dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " live in: (0010)\n" 169e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 170e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 171804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // then block 172dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " live in: (0100)\n" 173e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 174e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 175804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // return block 176e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 177e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 178e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0001)\n" 179804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // exit block 180e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 181e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 182e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n"; 183804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 184804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 185804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 186804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 187804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 188804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x200, 189804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 190804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 191804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 192804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 193804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 194804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 1954833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, CFG5) { 196804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 197804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // if (0 == 0) { 198804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } else { 199804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 200804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 201804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return a; 202e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // 203e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // Bitsets are made of: 204e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, phi) 205804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 206804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 207e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 208e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 209e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (110)\n" 210804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // block with if 211e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 212e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 213e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 214804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // else block 215e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 216e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 217e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 218804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // return block 219e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 220e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 221e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (001)\n" 222804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // exit block 223e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 224e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 225e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 226622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray "Block 5\n" // block to avoid critical edge. Predecessor is 1, successor is 3. 227e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (100)\n" 228e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 229e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n"; 230804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 231804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 232804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 233804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 3, 234804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 235804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 236804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 237804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 238804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 239804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 2404833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop1) { 241804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Simple loop with one preheader and one back edge. 242804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 243804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // while (a == a) { 244804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 245804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 246804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return; 247e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // Bitsets are made of: 248e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, phi) 249804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 250804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" // entry block 251e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 252e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 253e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (110)\n" 254804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" // pre header 255e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 256e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 257e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 258804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 259e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 260e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 261e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (001)\n" 262804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // back edge 263e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 264e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 265e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 266804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // return block 267e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 268e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 269e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 270804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // exit block 271e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 272e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 273e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n"; 274804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 275804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 276804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 277804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 278804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 279804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 280804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFD00, 281804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN_VOID); 282804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 283804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 284804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 285804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 2864833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop3) { 287804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Test that the returned value stays live in a preceding loop. 288804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 289804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // while (a == a) { 290804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 291804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 292804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return 5; 293e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // Bitsets are made of: 294dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // (constant0, constant5, constant4, phi) 295804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 296804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 297e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 298e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (1110)\n" 299e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (1110)\n" 300804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 301e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (1110)\n" 302e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 303e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 304804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 305e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0110)\n" 306e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 307e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0001)\n" 308804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // back edge 309e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0110)\n" 310e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0110)\n" 311e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 312804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // return block 313dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " live in: (0100)\n" 314e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 315e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n" 316804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // exit block 317e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (0000)\n" 318e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (0000)\n" 319e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (0000)\n"; 320804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 321804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 322804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 323804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 324804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 325804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFD00, 326804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 1 << 8, 327804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 1 << 8); 328804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 329804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 330804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 331804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 332804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 3334833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop4) { 334804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Make sure we support a preheader of a loop not being the first predecessor 335804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // in the predecessor list of the header. 336804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // var a = 0; 337804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // while (a == a) { 338804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // a = 4; 339804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // } 340804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // return a; 341804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 342e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, phi) 343804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 344804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 345e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 346e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 347e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (110)\n" 348804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 349e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 350e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (110)\n" 351e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 352804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 353e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 354e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (011)\n" 355e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (001)\n" 356804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" // back edge 357e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (010)\n" 358e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 359e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 360804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // pre loop header 361e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (110)\n" 362e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (010)\n" 363e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 364804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // return block 365e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (001)\n" 366e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 367e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n" 368804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // exit block 369e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (000)\n" 370e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (000)\n" 371e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (000)\n"; 372804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 373804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 374804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 375804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x500, 376804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 5, 377804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 378804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFD00, 379804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFC00, 380804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 381804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 382804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 383804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 384804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 3854833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop5) { 386804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Make sure we create a preheader of a loop when a header originally has two 387804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // incoming blocks and one back edge. 388804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 389dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // (constant0, constant5, constant4, phi in block 8) 390804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 391804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 3923afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0000)\n" 3933afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (1110)\n" 3943afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (1110)\n" 395804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 3963afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (1110)\n" 3973afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0110)\n" 3983afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 399804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" 400dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " live in: (0010)\n" 4013afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4023afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 403804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" 404dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " live in: (0100)\n" 4053afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4063afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 407804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // loop header 4083afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0001)\n" 4093afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0001)\n" 4103afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 411804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // back edge 4123afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0001)\n" 4133afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0001)\n" 4143afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 415804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // return block 4163afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0001)\n" 4173afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4183afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 419804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 7\n" // exit block 4203afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0000)\n" 4213afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0000)\n" 4223afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0000)\n" 423804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 8\n" // synthesized pre header 4243afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live in: (0000)\n" 4253afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " live out: (0001)\n" 4263afca781086699e60a8941fb9474d4607c5909cbNicolas Geoffray " kill: (0001)\n"; 427804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 428804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 429804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 430804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 431804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 432804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x200, 433804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 434804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 3, 435804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFE00, 436804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 437804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 438804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 439804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 440804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 4414833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop6) { 442804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 443db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray // (constant0, constant4, constant5, phi in block 2) 444804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 445804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 446db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0000)\n" 447db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (1110)\n" 448db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (1110)\n" 449804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 450db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (1110)\n" 451db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 452db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 453804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 454db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 455db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0111)\n" 456db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0001)\n" 457804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" 458db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 459db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 460db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 461db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray "Block 4\n" // back edge 462db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 463db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 464db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 465db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray "Block 5\n" // back edge 466db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0110)\n" 467db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0110)\n" 468db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 469804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // return block 470db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0001)\n" 471db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0000)\n" 472db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n" 473804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 7\n" // exit block 474db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live in: (0000)\n" 475db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " live out: (0000)\n" 476db216f4d49ea1561a74261c29f1264952232728aNicolas Geoffray " kill: (0000)\n"; 477804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 478804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 479804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 480804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 8, 481804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 482804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 483804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 484804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xFA00, 485804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xF900, 486804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 487804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 488804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 489804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 490804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 491804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 4924833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop7) { 493804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Bitsets are made of: 494e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray // (constant0, constant4, constant5, phi in block 2, phi in block 6) 495804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const char* expected = 496804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 0\n" 497e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00000)\n" 498e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (11100)\n" 499e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (11100)\n" 500804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 1\n" 501e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (11100)\n" 502e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01100)\n" 503e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 504804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 2\n" // loop header 505e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (01100)\n" 506e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01110)\n" 507e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00010)\n" 508804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 3\n" 509e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (01100)\n" 510e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01100)\n" 511e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 512804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 4\n" // loop exit 513e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00100)\n" 514e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 515e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 516804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 5\n" // back edge 517e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (01100)\n" 518e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (01100)\n" 519e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 520804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 6\n" // return block 521e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00000)\n" 522e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 523e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00001)\n" 524804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray "Block 7\n" // exit block 525e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00000)\n" 526e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 527e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n" 528622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray "Block 8\n" // synthesized block to avoid critical edge. 529e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live in: (00010)\n" 530e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " live out: (00000)\n" 531e50383288a75244255d3ecedcc79ffe9caf774cbNicolas Geoffray " kill: (00000)\n"; 532804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 533804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 534804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 0 | 0, 535804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 8, 536804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 4 << 12 | 0, 537804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::IF_EQ, 4, 538804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::CONST_4 | 5 << 12 | 0, 539804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0x0200, 540804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::GOTO | 0xF900, 541804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray Instruction::RETURN | 0 << 8); 542804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 543804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray TestCode(data, expected); 544804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 545804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 5464833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(LivenessTest, Loop8) { 5478ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // var a = 0; 5488ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // while (a == a) { 5498ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // a = a + a; 5508ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // } 5518ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // return a; 5528ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // 5538ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // We want to test that the ins of the loop exit 5548ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // does contain the phi. 5558ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // Bitsets are made of: 5568ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray // (constant0, phi, add) 5578ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray const char* expected = 5588ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 0\n" 5598ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (000)\n" 5608ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (100)\n" 5618ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (100)\n" 5628ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 1\n" // pre loop header 5638ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (100)\n" 5648ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5658ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (000)\n" 5668ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 2\n" // loop header 5678ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (000)\n" 5688ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (010)\n" 5698ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (010)\n" 5708ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 3\n" // back edge 5718ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (010)\n" 5728ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5738ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (001)\n" 5748ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 4\n" // return block 5758ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (010)\n" 5768ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5778ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (000)\n" 5788ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray "Block 5\n" // exit block 5798ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live in: (000)\n" 5808ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " live out: (000)\n" 5818ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray " kill: (000)\n"; 5828ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 5838ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 5848ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::CONST_4 | 0 | 0, 5858ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::IF_EQ, 6, 5868ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::ADD_INT, 0, 0, 5878ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::GOTO | 0xFB00, 5888ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray Instruction::RETURN | 0 << 8); 5898ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 5908ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray TestCode(data, expected); 5918ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray} 5928ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 593804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} // namespace art 594