On Dec 7, 2007 4:42 PM, Evan Cheng <[EMAIL PROTECTED]> wrote:
>
> Nicely done!
>
Thx! :-)
> > + // Map the def of a virtual register to the machine instruction.
> > + std::map<unsigned, const MachineInstr*> VRegDefs;
>
> Consider using IndexedMap.
>
Okay.
> > + bool CanHoistInst(MachineInstr &I) const {
> > + const TargetInstrDescriptor *TID = I.getInstrDescriptor();
> > + MachineOpCode Opcode = TID->Opcode;
> > +
> > + return TII->isTriviallyReMaterializable(&I) &&
> > + // FIXME: Below necessary?
> > + !(TII->isReturn(Opcode) ||
> > + TII->isTerminatorInstr(Opcode) ||
> > + TII->isBranch(Opcode) ||
> > + TII->isIndirectBranch(Opcode) ||
> > + TII->isBarrier(Opcode) ||
> > + TII->isCall(Opcode) ||
> > + TII->isLoad(Opcode) || // TODO: Do loads and stores.
> > + TII->isStore(Opcode));
> > + }
>
> Since you are touching this... When you have a chance, please rename
> it to something like hasNoSideEffect().
>
Okay. I'll do it in a future patch.
> > + void MoveInstToBlock(MachineBasicBlock *MBB, MachineInstr *MI) {
> > + MachineBasicBlock::iterator Iter = MBB->getFirstTerminator();
> > + MBB->insert(Iter, MI);
> > + }
>
> Poorly named. :-) MoveInstToEndOfBlock?
>
Sounds good.
> > + // Visit all of the instructions of the loop. We want to visit
> > the subloops
> > + // first, though, so that we can hoist their invariants first
> > into their
> > + // containing loop before we process that loop.
> > + SmallVector<MachineLoop*, 16> Loops;
> > + GatherAllLoops(L, Loops);
>
> Seems to me this can be smarter. When you are gathering the loops, put
> loops of greater depth in the front of the queue then HoistRegion
> won't have to check if the BB is in the current loop level?
>
> > + for (MachineBasicBlock::const_iterator
> > + II = MBB.begin(), IE = MBB.end(); II != IE; ++II) {
> > + const MachineInstr &MI = *II;
> > +
> > + if (MI.getNumOperands() > 0) {
> > + const MachineOperand &MO = MI.getOperand(0);
>
> This is not right. You are assuming only one def and it must be the
> first operand. Neither is necessarily true.
>
Okay.
> > + // If this subregion is not in the top level loop at all, exit.
> > + if (!CurLoop->contains(BB)) return;
> > +
> > + // Only need to process the contents of this block if it is not
> > part of a
> > + // subloop (which would already have been processed).
> > + if (!isInSubLoop(BB))
>
> Like I said earlier, I think this check can be eliminated if we visit
> the inner most loops first (and perhaps keep track which BB has been
> processed?)
>
I'm not sure I understand. I was under the impression that
MachineDomTreeNode would give blocks from the loop and its subloops.
If we keep track of those visited, I suppose we could simplify this
check...
> > + // Try hoisting the instruction out of the loop. We can only
> > do this if
> > + // all of the operands of the instruction are loop invariant
> > and if it is
> > + // safe to hoist the instruction.
> > + if (Hoist(MI))
> > + // Hoisting was successful! Remove bothersome instruction
> > now.
> > + MI.getParent()->remove(&MI);
>
> Why not have Hoist remove the MI?
>
I had a bug earlier where I was invalidating an iterator. I think it's
no longer the case, so this can be moved to Hoist instead.
> > + // Don't hoist if this instruction implicitly reads physical
> > registers or
> > + // doesn't take any operands.
> > + if (TID->ImplicitUses || !I.getNumOperands()) return false;
>
> The comment is wrong. It's ok to lift something that has no uses but
> produces result(s), right? "doesn't take any operands" to me means
> something that doesn't have any uses.
>
I was thinking about things like "emms" which don't seem to use
anything, but have definite side effects. Or will this be picked up in
the earlier check isTriviallyReMaterializable?
> > + if (!CanHoistInst(I)) return false;
>
> Perhaps fold the earlier check into CanHoistInst()?
>
Okay.
> > + // If the loop contains the definition of an operand, then the
> > instruction
> > + // isn't loop invariant.
> > + if (CurLoop->contains(VRegDefs[Reg]->getParent()))
> > + return false;
>
> Hmmm. I am not sure about this. What if the definition is in the
> preheader? Does contains() returns true? Chris, Owen?
>
The preheader wouldn't be part of the loop, so it should be okay.
> Also, I fear this might be slow. When you are creating the VReg -> MI
> map, perhaps you should create a VReg -> loop map as well?
>
I'll see if a map will help things along.
> > +bool MachineLICM::Hoist(MachineInstr &MI) {
> > + if (!isLoopInvariantInst(MI)) return false;
> > +
> > + std::vector<MachineBasicBlock*> Preds;
> > +
> > + // Non-back-edge predecessors.
> > + FindPredecessors(Preds);
>
> Consider caching some of these info?
>
Okay.
> > + // FIXME: We are assuming at first that the basic blocks coming
> > into this
> > + // loop have only one successor each. This isn't the case in
> > general because
> > + // we haven't broken critical edges or added preheaders.
> > + if (MBB->succ_size() != 1) return false;
> > + assert(*MBB->succ_begin() == CurLoop->getHeader() &&
> > + "The predecessor doesn't feed directly into the loop
> > header!");
> > + }
>
> Are we going to create a preheader to hoist LICM to? Then we won't
> need to do all these checking? I am entirely sure about it. Someone
> please chime in.
>
We want a pre-header. That will come at a later time. I just wanted to
"walk" before running. :-) But, yes, a lot of the checks for
predecessors will be simplified then.
> > + // Now move the instructions to the predecessors.
> > + for (std::vector<MachineBasicBlock*>::iterator
> > + I = Preds.begin(), E = Preds.end(); I != E; ++I)
> > + MoveInstToBlock(*I, MI.clone());
>
> This will create multiple copies, it seems bad. Again, this should be
> fixable with a loop preheader?
>
As Chris pointed out, it's filled with fail because of phi nodes, etc.
I made it more strict wrt the predecessors. Now there can only be one
(like in Highlander). Eventually, that one will be the pre-header.
> Very nice first cut!
>
Thanks! :-)
-bw
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
