C-Breeze C Compiler Infrastructure [ Project home page]

lir_gen_walker.cc Go to the documentation of this file. // $Id: lir_gen_walker.cc,v 1.10 2003/08/11 17:38:52 abrown Exp $ // ---------------------------------------------------------------------- // // C-Breeze // C Compiler Framework // // Copyright (c) 2002 University of Texas at Austin // // Chuck Tsen // Charles Nevill // Paul Arthur Navratil // Calvin Lin // // Permission is hereby granted, free of charge, to any person // obtaining a copy of this software and associated documentation // files (the "Software"), to deal in the Software without // restriction, including without limitation the rights to use, copy, // modify, merge, publish, distribute, sublicense, and/or sell copies // of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice shall be // included in all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND // NONINFRINGEMENT. IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT // AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF // OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN // THE SOFTWARE. // // We acknowledge the C-to-C Translator from MIT Laboratory for // Computer Science for inspiring parts of the C-Breeze design. // // ---------------------------------------------------------------------- #include <functional> #include <algorithm> #include "c_breeze.h" #include "ref_clone_changer.h" #include "lir_gen_walker.h" #include "lirutil.h" map<unsigned int, BinaryInstProc> lir_gen_walker::binary_map; map<unsigned int, UnaryInstProc> lir_gen_walker::unary_map; map<unsigned int, Compare_type> lir_gen_walker::opid_cmptype_map; lir_gen_walker::lir_gen_walker() : Walker(Both, Subtree), _unit(0), _proc(0) { if ( binary_map.empty() || unary_map.empty() || opid_cmptype_map.empty() ) init_maps(); } void lir_gen_walker::init_maps(void) { binary_map['+'] = &LIR::Add; binary_map['*'] = &LIR::Mul; binary_map['/'] = &LIR::Div; binary_map['-'] = &LIR::Sub; binary_map['%'] = &LIR::Mod; binary_map['&'] = &LIR::BitwiseAND; binary_map['|'] = &LIR::BitwiseOR; binary_map['^'] = &LIR::BitwiseXOR; binary_map[Operator::LS] = &LIR::BitwiseShiftLeft; binary_map[Operator::RS] = &LIR::BitwiseShiftRight; unary_map['~'] = &LIR::BitwiseNOT; unary_map[Operator::UMINUS] = &LIR::Neg; opid_cmptype_map[Operator::EQ] = cmp_EQ; opid_cmptype_map[Operator::NE] = cmp_NE; opid_cmptype_map['<'] = cmp_LT; opid_cmptype_map[Operator::LE] = cmp_LE; opid_cmptype_map['>'] = cmp_GT; opid_cmptype_map[Operator::GE] = cmp_GE; } void lir_gen_walker::at_unit(unitNode * the_unit, Order ord) { if ( ord == Preorder ) { the_unit->instructions().clear(); _unit = the_unit; AllocSizeChanger::size(the_unit); for ( def_list_p p = the_unit->defs().begin(); p != the_unit->defs().end(); p++ ) gen_global_decl(*p); SizeofChanger soc; the_unit->change(soc); } else { // ord == Postorder _unit = NULL; #ifdef DEBUG // print out all LIR instructions at the unit level cout << "Initial unit LIR instruction listing:" << endl; instruction_list::const_iterator it = the_unit->instructions().begin(); int num = 0; while ( it != the_unit->instructions().end() ) cout << num++ << " " << **(it++) << endl; cout << endl << endl; #endif /* DEBUG */ } } void lir_gen_walker::at_proc(procNode * the_proc, Order ord) { if ( ord == Preorder ) { _alloc.reset(); _proc = the_proc; the_proc->instructions().clear(); the_proc->lir_blocks().clear(); // ??? int stackOffset = -1 * CBZ::ArchInfo.get_stack_extra_top(); the_proc->set_initial_stack_local_offset(stackOffset); // determine what variables must be allocated to memory AllocToMemWalker atmw; the_proc->walk(atmw); the_proc->instructions().push_back(LIR::BeginProc(the_proc)); // declare & allocate space for local variables for ( decl_list_p p = the_proc->body()->decls().begin(); p != the_proc->body()->decls().end(); p++ ) gen_local_decl(*p, atmw); // declare (& allocate space) for formal arguments if ( funcNode * the_func = dynamic_cast<funcNode *>(the_proc->decl()->type()) ) { for ( decl_list_p p = the_func->args().begin(); p != the_func->args().end(); p++ ) gen_arg_decl(*p, atmw); ; } else CBZFAIL(("procNode doesn't contain expected funcNode")); } else { // ord == Postorder the_proc->instructions().push_back(LIR::EndProc(the_proc)); _proc = NULL; #ifdef DEBUG // print out all of the instructions cout << "Initial proc LIR instruction listing:" << endl; instruction_list::const_iterator it = the_proc->instructions().begin(); int num = 0; while ( it != the_proc->instructions().end() ) cout << num++ << " " << **(it++) << endl; cout << endl << endl; #endif /* DEBUG */ } } void lir_gen_walker::at_threeAddr(threeAddrNode * the_3addr, Order ord) { if ( ord == Preorder ) { if ( the_3addr->lhs() ) gen_assignment(the_3addr); else if ( the_3addr->op() && the_3addr->op()->id() == Operator::FUNC_CALL ) gen_call(the_3addr); else CBZFAIL(("Ill-formed threeAddrNode")); } } void lir_gen_walker::at_goto(gotoNode *the_goto, Order ord){ if ( ord == Preorder ) { assert(the_goto->label()); gen_goto(the_goto); } } void lir_gen_walker::at_label(labelNode *the_label, Order ord){ if (ord == Preorder) gen_label(the_label); } void lir_gen_walker::at_conditiongoto(conditiongotoNode * the_condgoto, Order ord) { if ( ord == Preorder ) { assert(the_condgoto->left() && the_condgoto->right() && the_condgoto->label() && the_condgoto->op()->is_comparison()); gen_conditional_branch(the_condgoto); } } void lir_gen_walker::at_return(returnNode *the_return, Walker::Order ord) { if (ord == Preorder ) { assert(the_return->proc_exit()); gen_return(the_return); } } expr_list * lir_gen_walker::flatten_init(exprNode * expr) { expr_list * retlist = new expr_list; if ( initializerNode * init = dynamic_cast<initializerNode *>(expr) ) { for ( expr_list_p p = init->exprs().begin(); p != init->exprs().end(); p++) { expr_list * sublist = flatten_init(*p); retlist->splice(retlist->end(), *sublist); delete sublist; } } else retlist->push_back(expr); return retlist; } void lir_gen_walker::gen_global_decl(defNode * the_def) { if ( declNode * the_decl = dynamic_cast<declNode *>(the_def) ) { if ( the_decl->decl_location() == declNode::TOP && the_decl->storage_class() != declNode::TYPEDEF && the_decl->storage_class() != declNode::EXTERN ) { declNode::Storage_location & loc = the_decl->storage_location(); loc._type = declNode::Storage_location::storageloc_mem_global; // loc._global_size = the_decl->type()->alloc_size(); // loc._global_align = the_decl->type()->alloc_align(); if ( the_decl->init() ) { _unit->instructions().push_back(LIR::DeclareGlobal(the_decl)); _unit->instructions().push_back(LIR::Label(the_decl->name())); expr_list * inits = flatten_init(the_decl->init()); for (expr_list_p p = inits->begin(); p != inits->end(); p++ ) { // we rely on the proper type information, either in the constNode // or as a castNode is present in the initializer list. in this // way, we only need to traverse the initializer list, and not // the declNode type() (*p)->eval(); assert(!(*p)->value().no_val()); LirInst * newInst = NULL; // TODO: turn this into a lookup table typeNode * type = (*p)->no_tdef_type(); if ( type->is_pointer() ) if ( type->is_aggregate() ) newInst = LIR::StaticDataString((*p)->value()); else newInst = LIR::StaticDataInt((*p)->value()); else if ( primNode * prim = dynamic_cast<primNode *>(type) ) { basic_type basic = prim->basic(); if ( basic.is_char() ) newInst = LIR::StaticDataChar((*p)->value()); else if ( basic.is_int() ) if ( basic.is_short() ) newInst = LIR::StaticDataShort((*p)->value()); else if ( basic.is_long() ) newInst = LIR::StaticDataLong((*p)->value()); else newInst = LIR::StaticDataInt((*p)->value()); else if ( basic.is_float() ) if ( basic.is_long() ) newInst = LIR::StaticDataDouble((*p)->value()); else newInst = LIR::StaticDataSingle((*p)->value()); } assert(newInst); _unit->instructions().push_back(newInst); } // end for ( ... inits ... ) delete inits; } else { LirInst * newInst = LIR::StaticDataUninit(the_decl->name(), the_decl->type()->alloc_size()); _unit->instructions().push_back(newInst); } } } } void lir_gen_walker::gen_arg_decl(declNode * the_decl, AllocToMemWalker & atmw) { if ( the_decl->type()->is_void() ) return; assert(the_decl->decl_location() == declNode::FORMAL); declNode::Storage_location & loc = the_decl->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_unknown); Register reg; typeNode * type = the_decl->no_tdef_type(); assert(!type->is_ellipsis()); if ( _alloc.assign_arg_register(type, reg) ) { // argument will be assigned to a register loc._type = declNode::Storage_location::storageloc_register; loc._register = reg; } else { // argument will be pushed onto the stack int stackLoc = _alloc.assign_arg_stack(type); loc._type = declNode::Storage_location::storageloc_stack; loc._stack_offset = stackLoc; } _proc->instructions().push_back(LIR::DeclareLocal(the_decl)); if ( ( CBZ::NoRegAlloc || atmw.needsMem(the_decl) ) && loc._type != declNode::Storage_location::storageloc_stack ) { // it must live on the stack, but currently doesn't, so store it to the // stack upon entry to procedure assert(loc._type == declNode::Storage_location::storageloc_register); // create a temporary stack variable, so that we can allocate it declNode * tempDecl = LirUtil::new_auto_decl(type); _proc->alloc_stack_local(tempDecl); // use the storage allocated to the temporary for the argument declNode::Storage_location oldLoc = loc; loc = tempDecl->storage_location(); delete tempDecl; _proc->instructions().push_back(LIR::Store(type, oldLoc._register, the_decl, Register::getRegFp(), DATA_CONTENTS_FRAMEP, loc._stack_offset, NULL)); } } void lir_gen_walker::gen_local_decl(declNode * the_decl, AllocToMemWalker & atmw) { assert(the_decl->storage_class() != declNode::STATIC); assert(the_decl->decl_location() == declNode::BLOCK); declNode::Storage_location & loc = the_decl->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_unknown); if ( the_decl == _proc->return_decl() ) { // this is the decl for the return value from the procedure Register reg; if ( Register::getRegRetVal(the_decl->no_tdef_type(), reg) ) { loc._type = declNode::Storage_location::storageloc_register; loc._register = reg; } else { // must return the value on the stack // TODO assert(false); } } else if ( atmw.needsMem(the_decl) || CBZ::NoRegAlloc ) { _proc->alloc_stack_local(the_decl); } else { _alloc.assign_register(the_decl); } _proc->instructions().push_back(LIR::DeclareLocal(the_decl)); if ( the_decl->init() ) { // it has a non-scalar initializer assert(false); } } // a = ... void lir_gen_walker::gen_assignment(threeAddrNode * the_3addr) { if ( ! the_3addr->op() ) gen_simple_assignment(the_3addr); else if ( the_3addr->op()->is_binary() ) gen_binary_assignment(the_3addr); else if ( the_3addr->op()->is_unary() ) gen_unary_assignment(the_3addr); else if ( the_3addr->op()->id() == Operator::FUNC_CALL ) gen_call_assignment(the_3addr); else CBZFAIL(("Unknown assignment")); } // a = b void lir_gen_walker::gen_simple_assignment(threeAddrNode * the_3addr) { assert(the_3addr->rhs1()); typeNode * type = the_3addr->lhs()->type(); if ( type->is_scalar() ) { // really a simple assignment pair<Register, declNode *> loaded = gen_load(the_3addr->rhs1()); gen_store(the_3addr->lhs(), loaded.first, loaded.second); } else if ( structNode * the_struct = dynamic_cast<structNode *>(type) ) { // actually an assignment from one struct to another // TODO: implement a Memcpy LIR instruction & use it here assert(false); } else CBZFAIL(("Invalid simple assignment")); } // a = <unop> b void lir_gen_walker::gen_unary_assignment(threeAddrNode * the_3addr) { pair<Register, declNode *> rhsLoaded = gen_load(the_3addr->rhs1()); // do the operation Register resultReg; declNode * resultDecl = NULL; _alloc.get_temp_var(the_3addr->lhs()->type(), resultReg, resultDecl); LirInst * new_inst = unary_map[the_3addr->op()->id()](the_3addr->lhs()->type(), resultReg, resultDecl, rhsLoaded.first, rhsLoaded.second); _proc->instructions().push_back(new_inst); gen_store(the_3addr->lhs(), resultReg, resultDecl); } // a = b <binop> c void lir_gen_walker::gen_binary_assignment(threeAddrNode * the_3addr) { pair<Register, declNode *> rhs1Loaded; pair<Register, declNode *> rhs2Loaded; bool rhs1Pointer = ( the_3addr->rhs1()->type()->typ() == Ptr ); bool rhs2Pointer = ( the_3addr->rhs2()->type()->typ() == Ptr ); // handle pointer arithmetic if ( ( rhs1Pointer && ! rhs2Pointer ) || ( rhs2Pointer && !rhs1Pointer ) ) { // TODO: check C lang. spec. about this. assert(the_3addr->op()->id() == '-' || the_3addr->op()->id() == '+'); operandNode * ptrNode = NULL; operandNode * intNode = NULL; if ( rhs1Pointer ) { ptrNode = the_3addr->rhs1(); intNode = the_3addr->rhs2(); } else { ptrNode = the_3addr->rhs2(); intNode = the_3addr->rhs1(); } typeNode * typePointed = ptrNode->noncast_type(false)->type(); int size = typePointed->alloc_size(); if ( size != 1 ) { // TODO: fold the potential constants here (or later in constant // prop/folding phase) pair<Register, declNode *> ptrLoaded = gen_load(ptrNode); pair<Register, declNode *> intLoaded = gen_load(intNode); Register prodReg; declNode * prodDecl; _alloc.get_temp_var(intNode->type(), prodReg, prodDecl); reg_or_const sizeConst = constant::constant(size); _proc->instructions().push_back(LIR::Mul(intNode->type(), prodReg, prodDecl, intLoaded.first, intLoaded.second, sizeConst, NULL)); // TODO: correct/safe? rhs1Loaded = ptrLoaded; rhs2Loaded = pair<Register, declNode *>(prodReg, prodDecl); } else { // size == 1 rhs1Loaded = gen_load(the_3addr->rhs1()); rhs2Loaded = gen_load(the_3addr->rhs2()); } } else { // not dealing with pointer arithmetic, just normal rhs1Loaded = gen_load(the_3addr->rhs1()); // TODO: avoid 'reloading' if same as rhs1 rhs2Loaded = gen_load(the_3addr->rhs2()); } // do the actual operation Register resultReg; declNode * resultDecl = NULL; _alloc.get_temp_var(the_3addr->lhs()->type(), resultReg, resultDecl); LirInst * new_inst = binary_map[the_3addr->op()->id()](the_3addr->lhs()->type(), resultReg, resultDecl, rhs1Loaded.first, rhs1Loaded.second, rhs2Loaded.first, rhs2Loaded.second); _proc->instructions().push_back(new_inst); gen_store(the_3addr->lhs(), resultReg, resultDecl); } // a = b(...) void lir_gen_walker::gen_call_assignment(threeAddrNode * the_3addr) { gen_call(the_3addr); typeNode * type = the_3addr->lhs()->type(); if ( type->is_scalar() ) { Register reg; if ( Register::getRegRetVal(type, reg) ) { gen_store(the_3addr->lhs(), reg, DATA_CONTENTS_RETVAL); } else CBZFAIL(("No return register for scalar type")); } else { // return value is NOT in a register assert(false); } } void lir_gen_walker::gen_conditional_branch(conditiongotoNode * the_condgoto) { pair<Register, declNode *> leftLoaded = gen_load(the_condgoto->left()); pair<Register, declNode *> rightLoaded = gen_load(the_condgoto->right()); _proc->instructions().push_back(LIR::Compare(leftLoaded.first, leftLoaded.second, rightLoaded.first, rightLoaded.second)); LirInst * new_inst = LIR::Branch(opid_cmptype_map[the_condgoto->op()->id()], the_condgoto->label()->name()); _proc->instructions().push_back(new_inst); } void lir_gen_walker::gen_goto(gotoNode * the_goto) { _proc->instructions().push_back(LIR::Jmp(the_goto->name())); } void lir_gen_walker::gen_label(labelNode * the_label) { _proc->instructions().push_back(LIR::Label(the_label->name())); } void lir_gen_walker::gen_return(returnNode * the_return) { // if a value is returned, it will have been taken care of by // the register (or stack) allocation of the declNode corresponding // to the return value for the proc, so we just need to put the 'Return' in _proc->instructions().push_back(LIR::Return(_proc)); } void lir_gen_walker::gen_call(threeAddrNode * the_3addr) { // add sequencing instruction _proc->instructions().push_back(LIR::CallPre()); operand_list & args = the_3addr->arg_list(); operand_list_p currArg = args.begin(); int nextFixed = 0; int nextFloat = 0; Register currReg; const arch_info::register_info_list & fixedRegs = CBZ::ArchInfo.get_regs_param_fixed(); const arch_info::register_info_list & floatRegs = CBZ::ArchInfo.get_regs_param_float(); int stack_arg_bytes = 0; int nextStackOffset = CBZ::ArchInfo.get_stack_extra_bottom(); while ( currArg != args.end() ) { bool isFloat = (*currArg)->type()->is_float(); bool isFixed = (*currArg)->type()->is_integer() || (*currArg)->type()->is_pointer(); if ( isFloat && nextFloat < floatRegs.size() ) { currReg = *(floatRegs[nextFloat++]); pair<Register, declNode *> argLoaded = gen_load(*currArg); gen_move(currReg, DATA_CONTENTS_REG_OUT, argLoaded.first, argLoaded.second); } else if ( isFixed && nextFixed < fixedRegs.size() ) { currReg = *(fixedRegs[nextFixed++]); pair<Register, declNode *> argLoaded = gen_load(*currArg); gen_move(currReg, DATA_CONTENTS_REG_OUT, argLoaded.first, argLoaded.second); } else { // push the argument onto the stack // update stack_arg_bytes typeNode * argType = (*currArg)->type(); AllocSizeChanger::size(argType); int align = argType->alloc_align(); int size = argType->alloc_size(); nextStackOffset = ((nextStackOffset + align - 1) / align ) * align; if ( (*currArg)->type()->is_scalar() ) { pair<Register, declNode *> argLoaded = gen_load(*currArg); _proc->instructions().push_back(LIR::Store((*currArg)->type(), argLoaded.first, argLoaded.second, Register::getRegSp(), DATA_CONTENTS_STACKP, nextStackOffset, NULL)); } else { // copy the arg onto the stack // TODO: implement Memcpy LIR instruction & use it here assert(false); } nextStackOffset += size; stack_arg_bytes += size; } currArg++; } // end while ( currArg != args.end() ) _proc->instructions().push_back(LIR::Call(the_3addr, stack_arg_bytes)); } pair<Register, declNode *> lir_gen_walker::gen_load(indexNode * the_index) { if ( idNode * the_id = dynamic_cast<idNode *>(the_index) ) { if ( the_id->decl()->decl_location() == declNode::TOP ) return load_global_var(the_id); else return load_stack_var(the_id); } else if ( constNode * the_const = dynamic_cast<constNode *>(the_index) ) { return load_const(the_const); } else CBZFAIL(("Unknown indexNode")); } pair<Register, declNode *> lir_gen_walker::gen_load(operandNode * the_oper) { if ( idNode * the_id = dynamic_cast<idNode *>(the_oper->var()) ) { if ( the_id->decl()->decl_location() == declNode::TOP ) return load_global(the_oper); else return load_stack(the_oper); } else if (constNode * the_const = dynamic_cast<constNode*>(the_oper->var())) { assert(the_oper->fields().empty() && !the_oper->index()); return load_const(the_const); } else CBZFAIL(("Malformed operandNode")); } int lir_gen_walker::field_offset(operandNode * the_oper) { int offset = 0; typeNode * containingType = the_oper->var()->type()->follow_tdefs(); if ( the_oper->star() ) containingType = containingType->type()->follow_tdefs(); for ( id_list_p operField = the_oper->fields().begin(); operField != the_oper->fields().end(); operField++ ) { if ( structNode * containingStruct = dynamic_cast<structNode *>(containingType) ) { suespecNode * suespec = containingStruct->spec(); assert(suespec); for ( decl_list_p structField = suespec->fields().begin(); structField != suespec->fields().end() && (*structField) != (*operField)->decl(); structField++ ) { int align = (*structField)->type()->alloc_align(); int size = (*structField)->type()->alloc_size(); offset = (( (offset + size) + align - 1) / align) * align; // cout << size << " / " << align << " @ " << offset << endl; } } containingType = (*operField)->decl()->type()->follow_tdefs(); } typeNode * type = the_oper->type(); // the_oper->noncast_type(false)? AllocSizeChanger::size(type); int align = type->alloc_align(); offset = (( offset + align - 1) / align) * align; // cout << ">>>>>>>>" << offset << endl; return offset; } pair<reg_or_const, declNode *> lir_gen_walker::index_offset ( operandNode * the_oper ) { if ( the_oper->index() ) { typeNode * elmtType = the_oper->noncast_type(false); // must ensure that potentially new ptrNode has the right size int elmtSize = elmtType->alloc_size(); if ( idNode * idIndex = dynamic_cast<idNode *>(the_oper->index()) ) { pair<Register, declNode *> indexLoaded = gen_load(idIndex); Register resultReg; declNode * resultDecl; primNode * intType = new primNode(basic_type::Int); _alloc.get_temp_var(intType, resultReg, resultDecl); _proc->instructions().push_back(LIR::Mul(intType, resultReg, resultDecl, indexLoaded.first, indexLoaded.second, constant::constant(elmtSize), NULL)); return pair<reg_or_const, declNode *>(resultReg, resultDecl); } else { constNode * constIndex = dynamic_cast<constNode *>(the_oper->index()); assert(constIndex); constant constVal = elmtSize * constIndex->value().Integer(); return pair<reg_or_const, declNode *>(constVal, NULL); } } // !the_oper->index() return pair<reg_or_const, declNode *>(constant::constant(0), NULL); } pair<Register, declNode *> lir_gen_walker::load_global(operandNode * the_oper) { if ( the_oper->addr() ) { // want the effective address of the thing return load_global_ea(the_oper); } else if ( arrayNode * arrayType = dynamic_cast<arrayNode *>(the_oper->noncast_type(false)) ) { // result is an "array", aka: a pointer into an array return load_global_ea(the_oper); } else { // we want the value in the location return load_global_value(the_oper); } } // TODO: factor common code from load_stack_ea pair<Register, declNode *> lir_gen_walker::load_global_ea ( operandNode * the_oper ) { idNode * the_id = dynamic_cast<idNode *>(the_oper->var()); assert(the_id); int fieldOffset = field_offset(the_oper); pair<reg_or_const, declNode *> indexOffset = index_offset(the_oper); pair<Register, declNode *> base; if ( the_oper->star() ) base = load_global_var(the_id); else base = load_global_addr(the_id); if ( indexOffset.first._is_const ) { int offset = fieldOffset + indexOffset.first._const.Integer(); if ( offset ) { Register addrReg; declNode * addrDecl; _alloc.get_temp_ptr(addrReg, addrDecl); // TODO: determine when to add the immediate directly w/o load constNode * offsetConst = new constNode(constant::constant(offset)); pair<Register, declNode *> offLoaded = load_const(offsetConst); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), addrReg, addrDecl, base.first, base.second, offLoaded.first, offLoaded.second)); return pair<Register, declNode *>(addrReg, addrDecl); } else { // offset == 0 return base; } } else { // indexOffset is in a register if ( fieldOffset ) { Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); // TODO: determine when to add the immediate directly w/o load constNode * offsetConst = new constNode(constant::constant(fieldOffset)); pair<Register, declNode *> offLoaded = load_const(offsetConst); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, offLoaded.first, offLoaded.second)); base = pair<Register, declNode *>(tempReg, tempDecl); } Register addrReg; declNode * addrDecl; _alloc.get_temp_ptr(addrReg, addrDecl); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), addrReg, addrDecl, base.first, base.second, indexOffset.first._reg, indexOffset.second)); return pair<Register, declNode *>(addrReg, addrDecl); } } // TODO: factor common code from load_stack_value pair<Register, declNode *> lir_gen_walker::load_global_value ( operandNode * the_oper ) { idNode * the_id = dynamic_cast<idNode *>(the_oper->var()); assert(the_id); int fieldOffset = field_offset(the_oper); Register loadReg; declNode * loadDecl; _alloc.get_temp_var(the_oper->noncast_type(), loadReg, loadDecl); const declNode::Storage_location & loc = the_id->decl()->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_mem_global); if ( the_oper->index() ) { pair<reg_or_const, declNode *> indexOffset = index_offset(the_oper); int offset = fieldOffset; pair<Register, declNode *> base; if ( the_id->type()->typ() == Ptr ) { base = load_global_var(the_id); if ( the_oper->star() ) { // handles (*global) [.field]* '[' index ']' Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Load(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, constant::constant(0), NULL)); base = pair<Register, declNode *>(tempReg, tempDecl); } } else { base = load_global_addr(the_id); } if ( indexOffset.first._is_const ) offset += indexOffset.first._const.Integer(); else { // indexOffset is in a register // TODO: see note w/ LIR::LoadStatic Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, indexOffset.first._reg, indexOffset.second)); base = pair<Register, declNode *>(tempReg, tempDecl); } _proc->instructions().push_back(LIR::Load(the_oper->noncast_type(), loadReg, loadDecl, base.first, base.second, constant::constant(offset), NULL)); } else { if ( the_oper->star() ) { pair<Register, declNode *> base = load_global_var(the_id); LirInst * newInst = LIR::Load(the_oper->noncast_type(), loadReg, loadDecl, base.first, base.second, constant::constant(fieldOffset), NULL); _proc->instructions().push_back(newInst); } else { LirInst * newInst = LIR::LoadStatic(the_oper->noncast_type(), loadReg, loadDecl, the_id->name(), the_id->decl(), constant::constant(fieldOffset), NULL); _proc->instructions().push_back(newInst); } } if ( needs_conversion(the_oper->noncast_type(), the_oper->type()) ) return gen_conversion(the_oper->type(), loadReg, loadDecl); else return pair<Register, declNode *>(loadReg, loadDecl); } pair<Register, declNode *> lir_gen_walker::load_global_var(idNode * the_id) { const declNode::Storage_location & loc = the_id->decl()->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_mem_global); Register reg; declNode * regDecl; _alloc.get_temp_var(the_id->type(), reg, regDecl); _proc->instructions().push_back(LIR::LoadStatic(the_id->type(), reg, regDecl, the_id->name(), the_id->decl(), constant::constant(0), NULL)); return pair<Register, declNode *>(reg, regDecl); } pair<Register, declNode *> lir_gen_walker::load_global_addr(idNode * the_id) { const declNode::Storage_location & loc = the_id->decl()->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_mem_global); Register reg; declNode * regDecl; _alloc.get_temp_ptr(reg, regDecl); _proc->instructions().push_back(LIR::GetGlobalAddress(reg, regDecl, the_id->name(), the_id->decl(), constant::constant(0), NULL)); return pair<Register, declNode *>(reg, regDecl); } pair<Register, declNode *> lir_gen_walker::load_stack(operandNode * the_oper) { if ( the_oper->addr() ) { // we want the effective address of the thing return load_stack_ea(the_oper); } else if ( arrayNode * arrayType = dynamic_cast<arrayNode *>(the_oper->noncast_type(false)) ) { // result is an "array", aka: a pointer into an array return load_stack_ea(the_oper); } else { // we want the value in the location return load_stack_value(the_oper); } } // TODO: factor common code from load_global_ea pair<Register, declNode *> lir_gen_walker::load_stack_ea ( operandNode * the_oper ) { idNode * the_id = dynamic_cast<idNode *>(the_oper->var()); assert(the_id); int fieldOffset = field_offset(the_oper); pair<reg_or_const, declNode *> indexOffset = index_offset(the_oper); pair<Register, declNode *> base; if ( the_oper->star() ) base = load_stack_var(the_id); else base = load_stack_addr(the_id); if ( indexOffset.first._is_const ) { int offset = fieldOffset + indexOffset.first._const.Integer(); if ( offset ) { Register addrReg; declNode * addrDecl; _alloc.get_temp_ptr(addrReg, addrDecl); // TODO: determine when to add the immediate directly w/o load constNode * offsetConst = new constNode(constant::constant(offset)); pair<Register, declNode *> offLoaded = load_const(offsetConst); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), addrReg, addrDecl, base.first, base.second, offLoaded.first, offLoaded.second)); return pair<Register, declNode *>(addrReg, addrDecl); } else { // offset == 0 return base; } } else { // indexOffset is in a register if ( fieldOffset ) { Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); // TODO: determine when to add the immediate directly w/o load constNode * offsetConst = new constNode(constant::constant(fieldOffset)); pair<Register, declNode *> offLoaded = load_const(offsetConst); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, offLoaded.first, offLoaded.second)); base = pair<Register, declNode *>(tempReg, tempDecl); } Register addrReg; declNode * addrDecl; _alloc.get_temp_ptr(addrReg, addrDecl); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), addrReg, addrDecl, base.first, base.second, indexOffset.first._reg, indexOffset.second)); return pair<Register, declNode *>(addrReg, addrDecl); } } // TODO: factor common code from load_global_value pair<Register, declNode *> lir_gen_walker::load_stack_value ( operandNode * the_oper ) { idNode * the_id = dynamic_cast<idNode *>(the_oper->var()); assert(the_id); int fieldOffset = field_offset(the_oper); Register loadReg; declNode * loadDecl; _alloc.get_temp_var(the_oper->noncast_type(), loadReg, loadDecl); const declNode::Storage_location & loc = the_id->decl()->storage_location(); pair<Register, declNode *> base; int offset = fieldOffset; if ( the_oper->index() ) { pair<reg_or_const, declNode *> indexOffset = index_offset(the_oper); if ( the_id->type()->typ() == Ptr ) { base = load_stack_var(the_id); if ( the_oper->star() ) { // handles: (*var) [.field]* '[' index ']' Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Load(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, constant::constant(0), NULL)); base = pair<Register, declNode *>(tempReg, tempDecl); } } else { base = pair<Register, declNode *>(Register::getRegFp(), DATA_CONTENTS_FRAMEP); offset += loc._stack_offset; } if ( indexOffset.first._is_const ) offset += indexOffset.first._const.Integer(); else { // indexOffset is in a register // TODO: this really should be handled as a register indirect with // register offset (see note w/ LIR::Load) Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, indexOffset.first._reg, indexOffset.second)); base = pair<Register, declNode *>(tempReg, tempDecl); } } else { if ( the_oper->star() ) base = load_stack_var(the_id); else if ( loc._type == declNode::Storage_location::storageloc_register ) { // we already have a register-allocated variable, so just return the // register it lives int assert(the_oper->fields().empty()); return pair<Register, declNode *>(loc._register, the_id->decl()); } else { base = pair<Register, declNode *>(Register::getRegFp(), DATA_CONTENTS_FRAMEP); offset += loc._stack_offset; } } _proc->instructions().push_back(LIR::Load(the_oper->noncast_type(), loadReg, loadDecl, base.first, base.second, constant::constant(offset), NULL)); if ( needs_conversion(the_oper->noncast_type(), the_oper->type()) ) return gen_conversion(the_oper->type(), loadReg, loadDecl); else return pair<Register, declNode *>(loadReg, loadDecl); } pair<Register, declNode *> lir_gen_walker::load_stack_var(idNode * the_id) { const declNode::Storage_location & loc = the_id->decl()->storage_location(); if ( loc._type == declNode::Storage_location::storageloc_register ) // already in a register return pair<Register, declNode *>(loc._register, the_id->decl()); else if ( loc._type == declNode::Storage_location::storageloc_stack ) { Register reg; declNode * regDecl; _alloc.get_temp_var(the_id->type(), reg, regDecl); _proc->instructions().push_back(LIR::Load(the_id->type(), reg, regDecl, Register::getRegFp(), DATA_CONTENTS_FRAMEP, loc._stack_offset, NULL)); return pair<Register, declNode *>(reg, regDecl); } else CBZFAIL(("Incorrect Storage_location for a local variable.")); } pair<Register, declNode *> lir_gen_walker::load_stack_addr(idNode * the_id) { const declNode::Storage_location & loc = the_id->decl()->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_stack); Register reg; declNode * regDecl; _alloc.get_temp_ptr(reg, regDecl); LirInst * new_inst = LIR::GetEffectiveAddress(reg, regDecl, Register::getRegFp(), DATA_CONTENTS_FRAMEP, loc._stack_offset, NULL); _proc->instructions().push_back(new_inst); return pair<Register, declNode *>(reg, regDecl); } // use when you are SURE that you want the constant loaded into a register pair<Register, declNode *> lir_gen_walker::load_const(constNode * the_const) { assert(the_const); Register destReg; declNode * destDecl; _alloc.get_temp_var(the_const->type(), destReg, destDecl); constant & const_val = the_const->value(); assert(!const_val.no_val()); if ( const_val.is_str() ) { // create a global declaration for this string literal & load the // effective address of the global into the variable declNode * temp_decl = LirUtil::new_static_global(the_const->type(), the_const); gen_global_decl(temp_decl); // _proc->instructions().push_back(LIR::LoadStatic(LirUtil::newVoidPtr(), // destReg, destDecl, // temp_decl->name(), // temp_decl, // constant::constant(0), // NULL)); _proc->instructions().push_back(LIR::GetGlobalAddress(destReg, destDecl, temp_decl->name(), temp_decl, constant(0), NULL)); } else if ( CBZ::ArchInfo.instruction_supports_immediate(mn_LoadImmediate, the_const->type(), const_val) ) { // we can handle this with loadimmediate _proc->instructions().push_back(LIR::LoadImmediate(the_const->type(), destReg, destDecl, const_val)); } else { // we must declare a static value & load it declNode * temp_decl = LirUtil::new_static_global(the_const->type(), the_const); gen_global_decl(temp_decl); _proc->instructions().push_back(LIR::LoadStatic(the_const->type(), destReg, destDecl, temp_decl->name(), temp_decl, constant::constant(0), NULL)); } return pair<Register, declNode *>(destReg, destDecl); } void lir_gen_walker::gen_store(operandNode * dest, Register reg, declNode * regDecl) { if ( idNode * the_id = dynamic_cast<idNode *>(dest->var()) ) { if ( the_id->decl()->decl_location() == declNode::TOP ) store_global(dest, reg, regDecl); else store_stack(dest, reg, regDecl); } else CBZFAIL(("Malformed operandNode for storing")); } // TODO: factor common code with store_stack void lir_gen_walker::store_global(operandNode * dest, Register reg, declNode * regDecl) { idNode * the_id = dynamic_cast<idNode *>(dest->var()); assert(the_id); int fieldOffset = field_offset(dest); const declNode::Storage_location & loc = the_id->decl()->storage_location(); assert(loc._type == declNode::Storage_location::storageloc_mem_global); if ( dest->index() ) { pair<reg_or_const, declNode *> indexOffset = index_offset(dest); pair<Register, declNode *> base; if ( the_id->type()->typ() == Ptr ) { base = load_global_var(the_id); if ( dest->star() ) { // handles: (*global) [.field]* '[' index ']' Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Load(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, constant::constant(0), NULL)); base = pair<Register, declNode *>(tempReg, tempDecl); } } else { if ( indexOffset.first._is_const ) { int offset = fieldOffset + indexOffset.first._const.Integer(); LirInst * newInst = LIR::StoreStatic(dest->type(), reg, regDecl, the_id->name(), the_id->decl(), constant::constant(offset), NULL); _proc->instructions().push_back(newInst); return; } else base = load_global_addr(the_id); } if ( indexOffset.first._is_const ) { int offset = fieldOffset + indexOffset.first._const.Integer(); LirInst * newInst = LIR::Store(dest->type(), reg, regDecl, base.first, base.second, constant::constant(offset), NULL); _proc->instructions().push_back(newInst); } else { // TODO: see note w/ LIR::StoreStatic Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, indexOffset.first._reg, indexOffset.second)); LirInst * newInst = LIR::Store(dest->type(), reg, regDecl, tempReg, tempDecl, constant::constant(fieldOffset), NULL); _proc->instructions().push_back(newInst); } } else { if ( dest->star() ) { pair<Register, declNode *> base = load_global_var(the_id); LirInst * newInst = LIR::Store(dest->type(), reg, regDecl, base.first, base.second, constant::constant(fieldOffset), NULL); _proc->instructions().push_back(newInst); } else { LirInst * newInst = LIR::StoreStatic(dest->type(), reg, regDecl, the_id->name(), the_id->decl(), constant::constant(fieldOffset), NULL); _proc->instructions().push_back(newInst); } } } // TODO: factor common code with store_global void lir_gen_walker::store_stack(operandNode * dest, Register reg, declNode * regDecl) { idNode * the_id = dynamic_cast<idNode *>(dest->var()); assert(the_id); int fieldOffset = field_offset(dest); const declNode::Storage_location & loc = the_id->decl()->storage_location(); pair<Register, declNode *> base; int offset = fieldOffset; if ( dest->index() ) { pair<reg_or_const, declNode *> indexOffset = index_offset(dest); if ( the_id->type()->typ() == Ptr ) { base = load_stack_var(the_id); if ( dest->star() ) { // handles: (*var) [.field]* '[' index ']' Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Load(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, constant::constant(0), NULL)); base = pair<Register, declNode *>(tempReg, tempDecl); } } else { base = pair<Register, declNode *>(Register::getRegFp(), DATA_CONTENTS_FRAMEP); offset += loc._stack_offset; } if ( indexOffset.first._is_const ) offset += indexOffset.first._const.Integer(); else { // indexOffset is in a register // TODO: this really should be handled as a register indirect with // register offset (see note w/ LIR::Load) Register tempReg; declNode * tempDecl; _alloc.get_temp_ptr(tempReg, tempDecl); _proc->instructions().push_back(LIR::Add(LirUtil::newVoidPtr(), tempReg, tempDecl, base.first, base.second, indexOffset.first._reg, indexOffset.second)); base = pair<Register, declNode *>(tempReg, tempDecl); } } else { if ( dest->star() ) base = load_stack_var(the_id); else if ( loc._type == declNode::Storage_location::storageloc_register ) { // we already have a register-allocated variable, so just perform // a register-to-register move assert(dest->fields().empty()); gen_move(loc._register, the_id->decl(), reg, regDecl); return; } else { base = pair<Register, declNode *>(Register::getRegFp(), DATA_CONTENTS_FRAMEP); offset += loc._stack_offset; } } _proc->instructions().push_back(LIR::Store(dest->type(), reg, regDecl, base.first, base.second, constant::constant(offset), NULL)); } void lir_gen_walker::gen_move(Register dest, declNode * destDecl, Register src, declNode * srcDecl) { _proc->instructions().push_back(LIR::Move(dest, destDecl, src, srcDecl)); } bool lir_gen_walker::needs_conversion(typeNode * in_memory, typeNode * in_reg) { return ( *in_memory != *in_reg ); } pair<Register, declNode *> lir_gen_walker::gen_conversion ( typeNode * targetType, Register srcReg, declNode * srcDecl ) { Register resultReg; declNode * resultDecl; _alloc.get_temp_var(targetType, resultReg, resultDecl); _proc->instructions().push_back(LIR::ConvertType(srcDecl->type(), srcReg, srcDecl, targetType, resultReg, resultDecl)); return pair<Register, declNode *>(resultReg, resultDecl); } AllocSizeChanger::AllocSizeChanger(void) : Changer(Both, Subtree, false) {} Node * AllocSizeChanger::at_prim(primNode * the_prim, Order ord) { if ( ord == Postorder ) { the_prim->alloc_size(CBZ::ArchInfo.get_data_size(the_prim)); the_prim->alloc_align(CBZ::ArchInfo.get_data_align(the_prim)); } return the_prim; } Node * AllocSizeChanger::at_decl(declNode * the_decl, Order ord) { if ( ord == Preorder ) { _decls.push(the_decl); } else { // ord == Postorder assert(_decls.top() == the_decl); _decls.pop(); } return the_decl; } Node * AllocSizeChanger::at_array(arrayNode * the_array, Order ord) { if ( ord == Postorder ) { if ( _decls.empty() || ( _decls.top()->decl_location() != declNode::FORMAL && _decls.top()->storage_class() != declNode::EXTERN ) ) { assert(the_array->dim()); the_array->dim()->eval(); assert(!the_array->dim()->value().no_val()); the_array->alloc_size(the_array->type()->alloc_size() * the_array->dim()->value().Integer()); the_array->alloc_align(the_array->type()->alloc_align()); } else { // it's really a pointer, from our point of view // TODO: should we make it a pointer? the_array->alloc_size(CBZ::ArchInfo.get_data_size_ptr()); the_array->alloc_align(CBZ::ArchInfo.get_data_align_ptr()); } } return the_array; } Node * AllocSizeChanger::at_ptr(ptrNode * the_ptr, Order ord) { if ( ord == Postorder ) { the_ptr->alloc_size(CBZ::ArchInfo.get_data_size(the_ptr)); the_ptr->alloc_align(CBZ::ArchInfo.get_data_align(the_ptr)); } return the_ptr; } Node * AllocSizeChanger::at_enum(enumNode * the_enum, Order ord) { if ( ord == Postorder ) { primNode unsignedInt(typeNode::NONE, basic_type::UInt); the_enum->alloc_size(CBZ::ArchInfo.get_data_size(&unsignedInt)); the_enum->alloc_align(CBZ::ArchInfo.get_data_align(&unsignedInt)); } return the_enum; } Node * AllocSizeChanger::at_union(unionNode * the_union, Order ord) { if ( ord == Postorder ) { int maxSize = -1; int maxAlign = -1; for ( decl_list_p p = the_union->spec()->fields().begin(); p != the_union->spec()->fields().end(); p++ ) { maxSize = max(maxSize, (*p)->type()->alloc_size()); maxAlign = max(maxAlign, (*p)->type()->alloc_align()); } the_union->alloc_size(maxSize); the_union->alloc_align(maxAlign); } return the_union; } Node * AllocSizeChanger::at_struct(structNode * the_struct, Order ord) { if ( ord == Postorder ) { int size = 0; int align = 0; for ( decl_list_p p = the_struct->spec()->fields().begin(); p != the_struct->spec()->fields().end(); p++ ) { size += (*p)->type()->alloc_size(); align = max(align, (*p)->type()->alloc_align()); // TODO: ??? } the_struct->alloc_size(size); the_struct->alloc_align(align); } return the_struct; } Node * AllocSizeChanger::at_tdef(tdefNode * the_tdef, Order ord) { if ( ord == Postorder ) { the_tdef->alloc_size(the_tdef->def()->alloc_size()); the_tdef->alloc_align(the_tdef->def()->alloc_align()); } return the_tdef; } Node * AllocSizeChanger::at_unary(unaryNode * the_unary, Order ord) { if ( ord == Postorder ) { if ( the_unary->op() && the_unary->op()->id() == Operator::SIZEOF ) { typeNode * sizeof_type = the_unary->sizeof_type(); assert(sizeof_type); ostringstream ost; ost << sizeof_type->alloc_size(); return new constNode(constant::constant(sizeof_type->alloc_size()), ost.str().c_str(), the_unary->coord()); } } return the_unary; } SizeofChanger::SizeofChanger(void) : Changer(Preorder, Subtree, false) {} Node * SizeofChanger::at_threeAddr(threeAddrNode * the_3addr, Order ord) { if ( typeNode * size_type = the_3addr->sizeof_type() ) { ostringstream ost; ost << size_type->alloc_size(); constNode * sizeConst = new constNode(constant::constant(size_type->alloc_size()), ost.str().c_str(), the_3addr->coord()); the_3addr->rhs1(new operandNode(sizeConst, the_3addr->coord())); the_3addr->sizeof_type(static_cast<typeNode *>(0)); } return the_3addr; } AllocToMemWalker::AllocToMemWalker(void) : Walker(Preorder, Subtree) {} bool AllocToMemWalker::needsMem(declNode * the_decl) { return ( find(_decls.begin(), _decls.end(), the_decl) != _decls.end() ); } void AllocToMemWalker::at_decl(declNode * the_decl, Order ord) { if ( the_decl->type()->is_aggregate() || the_decl->type()->typ() == Union ) { _decls.push_back(the_decl); cout << "Must alloc to memory " << the_decl->name() << endl; } } void AllocToMemWalker::at_operand(operandNode * the_oper, Order ord) { if ( the_oper->addr() && the_oper->fields().empty() && !the_oper->index() ) { if ( idNode * the_id = dynamic_cast<idNode *>(the_oper->var()) ) { typeNode * type = the_oper->type(); if ( ( type->is_float() || type->is_integer() || type->is_pointer() ) && the_id->decl()->decl_location() == declNode::BLOCK ) // we have a local variable whose address is taken, so it // must live in memory _decls.push_back(the_id->decl()); cout << "Must alloc to memory " << the_id->name() << endl; } } }

Generated on August 27, 2003
Back to the C-Breeze home page